33. 搜索旋转排序数组 - 力扣（LeetCode）

一、题目

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：​​​​​​​

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：​​​​​​​

输入：nums = [1], target = 0
输出：-1

提示：

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums 中的每个值都 独一无二
• 题目数据保证 nums 在预先未知的某个下标上进行了旋转
• -10^4 <= target <= 10^4

二、代码

class Solution {public int search(int[] nums, int target) {// 设置左右边界指针int l = 0;int r = nums.length - 1;// 开始二分while (l <= r) {// 计算中间下标int m = (l + r) >> 1;// 如果中间值正好等于target，直接返回下标mif (nums[m] == target) {return m;}// 如果三个下标位置的数相等，并且他们又不等于target（[L] == [M] == [R] != target），这种情况是没有办法二分的，因为无法确定断电在左侧还是在右侧if (nums[l] == nums[m] && nums[m] == nums[r]) {// 这种情况下让L往下走，L++，直到遇到一个不是num[M]的位置，在当前L...R上继续二分while (l != m && nums[l] == nums[m]) {l++;}// 执行到这里，有两种情况：// 1) L == M L...M都一路都相等// 2) 从L到M终于找到了一个不等的位置if (l == m) { // L...M 一路都相等// L一直往右，到M了，一路都是num[M]，那么在M+1到R上二分l = m + 1;continue;}}// 执行到这里，arr[M]一定是 != num的// [L] [M] [R] 不都一样的情况, 如何二分的逻辑// [L] != [M]if (nums[l] != nums[m]) {// 如果[L] < [M]，说明左侧是有序的，那么断点应该在右侧if (nums[l] < nums[m]) {// 如果target的范围就在左侧有序的范围内，那么我们就对左侧进行二分if (target >= nums[l] && target < nums[m]) {r = m - 1;// 否则，target就应该在无序的右侧，我们就去右侧进行二分} else {l = m + 1;}// 这个情况就是右侧是有序的，断点在左侧} else {// 如果target的范围就在右侧有序的范围内，那么我们就对右侧进行二分if (target > nums[m] && target <= nums[r]) {l = m + 1;// 否则，target就应该在无序的左侧，我们就去左侧进行二分 } else {r = m - 1;}}// [M] != [R]} else {// 如果[M] < [R]，说明右侧是有序的，那么断点应该在左侧if (nums[m] < nums[r]) {if (target > nums[m] && target <= nums[r]) {l = m + 1;} else {r = m - 1;}// 这个情况就是左侧是有序的，断点在右侧} else {if (target >= nums[l] && target < nums[m]) {r = m - 1;} else {l = m + 1;}}}}// 如果整个二分过程没有找到target，就说明数组中没有target，返回-1return -1;}
}

三、解题思路 

将数组分成左右两部分，如果[L] < [M]，那么说明左部分一定是有序的，断点一定在右侧。反之，如果[M] < [R]，那么说明右部分一定是有序的，断点一定在左侧。因为断点所在的那一侧一定会是[L] > [M]或[M] > [R]，这一点随便举例子就能发现。