leetcode题：33. 搜索旋转排序数组

题目

整数数组 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 。

示例 1：

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

示例 2：

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

分析情况

这个算法需要考虑4种情况

第一种（左右都有序，中间值正好在左有序的最大值）

计算出的中间值正好是左边升序的最大值，那么目标值分三种情况，

1. 在中间值的左边有序元素之中
2. 在中间值的右边有序元素之中
3. 没有目标元素值
   

第二种（左有序，右无序，中间值在左序范围内）

计算出的中间值不是左边升序的最大值，那么目标值可能存在四种情况

1. 可能在中间值左边的有序的值
2. 可能在中间值后面无序数组中的左边有序
3. 可能在中间值后面无序数组中的右边有序
4. 没有目标值
   

第三种（左无序，右有序，中间值在右序范围内）

计算出的中间值不是左边升序的最大值，那么目标值可能存在四种情况

1. 可能在中间值右边的有序序的值
2. 可能在中间值左边无序数组中的左边有序
3. 可能在中间值左边无序数组中的右边有序
4. 没有目标值
   

第四种（左右都有序，中间值正好在右有序的最小值）

1. 在中间值的左边有序元素之中
2. 在中间值的右边有序元素之中
3. 没有目标元素值
   

思路

每次循环都要找中间值和目标值匹配，不匹配时，我们就要移动左右指针，当选择移动哪一个指针到哪个位置的时候，我们就需要判断这四种情况，来确定移动的指针和位置。

如何确定这四种情况：

• 中间值大于数组的第一个值，说明中间值的左边是有序的
• 中间值小于数组的第一个值，说明中间值的左边是无序的

左有序

• 目标值小于第一个值且小于中间值，说明在中间值到第一个值之间，可在进行二分
• 目标值不符合，说明不再此范围，则在中间值的右边，则把left指针=mid+1操作，进行下一次二分查找

左无序

• 目标值大于中间值，且小于最后一个值，那么就在中间下标到最后一个下标之间，可进行下一次二分查找
• 如果不符合，说明不再此范围，则在中间值左边，则把right=mid-1操作，进行下一次二叉查找

核心思想：

• 根据左右指针的下标来缩小计算范围（二分法）
• 数组的第一个值和最后一个值来确定符合哪种情况，来移动左右指针

代码

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length; 
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2; 
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

图解

当目标值为1

当目标值为9时，另外一种情况

得到目标值