解法：二分查找
解题思路
这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。
可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。如下图：mid 左右总有一侧是有序的
问题是确定 mid 的哪一边是有序的，观察发现可以通过 mid 和 nums[0] 进行比较得到两种情况：
- nums[0] <= nums[mid] ：此时 mid 左边有序
- nums[0] > nums[mid] ：此时 mid 右边有序
也就是说我们有能力 确定哪边有序
而 target 则有三种情况：
- target 刚好在 mid 的位置，可以直接返回；
- target 在有序一边，范围缩小一半
- target 不在有序一边，范围也能缩小一半
所以思路就是：mid二分 → 确定哪边有序 → target是否在有序一边 → 缩小范围 → mid二分 → …
直到边界重合
算法流程
循环内进行：mid二分 → 确定哪边有序 → target是否在有序一边 → 缩小范围
代码
class Solution { public int search(int[] nums, int target) { int len = nums.length; // 特殊情况 if(len == 0) return -1; if(len == 1) return target == nums[0] ? 0 : -1;、 // 初始的左右边界 int l = 0, r = len - 1; while(l <= r) { int mid = (l+r)/2; if(nums[mid] == target) return mid; // 如果 mid 左侧有序 // 如果 target 在左侧有序测，缩小右边界到 mid - 1 // 否则说明 target 在右侧无序侧，缩小左边界到 mid + 1 if(nums[0] <= nums[mid]) { if(nums[0] <= target && target < nums[mid]) r = mid - 1; else l = mid + 1; } // 相反如果是 mid 右侧有序 // 如果 target 在右侧有序侧，缩小左边界到 mid + 1 // 否则说明 target 在左侧无序侧，缩小右边界到 mid - 1 else { if(nums[mid] < target && target <= nums[len-1]) l = mid + 1; else r = mid - 1; } } return -1; } }
细节
二分思路比较重要，一开始不要否定
