leetcode 33.在旋转排序数组中搜索

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

33.旋转有序数组中的搜索[中等]

有一个整数数组nums，按升序排序（值各不相同）。在传递给您的函数之前，nums可能被一个未知的枢轴索引k（1 <= 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，如果target在nums中，则返回target的索引，如果不在nums中，则返回-1。必须编写一个具有O(logn)时间复杂度的算法。

示例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

---

解法关键点：

• 只有在递增区间内，且数字大小在左右边界大小之内才能够收敛区间
  • 当[start, end]为递增区间时，只判断target和单边的关系，无法确定target是否在此区间，必须判断双边关系才能锁定target在此区间
  • 当[start, end]为非单调增区间时，则其中可能包含任何大小的数字，比start大或者小，比end大或者小都有可能，无法收敛
• 指定mid的位置之后，左右两部分可能都是递增序列，而不是递增+旋转递增的序列组合
• 可能存在(start+end)/2=start的情况，所以必须用+1或-1进行收敛
• 尝试收敛时，nums[mid] < target && target <= nums[end]为真时，nums[mid]和target一定不等，所以start可以被置为mid+1；为假时可以判断target在[start, mid]区间内，结合上面nums[mid] == target为假的条件，可以判断target如果存在则一定在[start, mid-1]区间内

class Solution {
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] <= nums[end]) {
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
}