【Leetcode 热题 100】33. 搜索旋转排序数组

问题背景

整数数组 $nums$ 按升序排列，数组中的值 互不相同 。
在传递给函数之前，$nums$ 在预先未知的某个下标 $k(0\le 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(logn)$ 的算法解决此问题。

数据约束

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

解题过程

可以用两次二分来解决，找到数组中的最小值，然后比较待查找目标和数组中最后一个元素的大小，到对应的范围上再来一次 二分查找 获得结果。
这题可以通过精确划分类别，用一次二分就解决。但是这种做法没有任何时空效率上的提升，反而会让代码可读性变得非常差，就不写了。

具体实现

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int minIndex = findMin(nums);
        if(target > nums[n - 1]) {
            return binarySearch(nums, target, 0, minIndex);
        }
        return binarySearch(nums, target, minIndex, n);
    }

    // Leetcode 153.找到数组中的最小值
    private int findMin(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while(left < right) {
            int mid = left + ((right - left) >>> 1);
            if(nums[mid] > nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // Leetcode 35.搜索插入位置
    private int binarySearch(int[] nums, int target, int left, int right) {
        while(left < right) {
            int mid = left + ((right - left) >>> 1);
            if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left] == target ? left : -1;
    }
}