在断层环境中应用二分法

题目链接-来源：力扣（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 。

示例 1：

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

思路：

旋转排序数组，某种程度上是有序的，因此考虑二分法。
阻碍我们流畅使用二分法的只有一个因素，就是数组旋转后会出现断层。但是断层有一定的规律。
我们可以将数组分为「较大部分」和「较小部分」，「较大部分」在前，「较小部分」在后。当数组没有发生旋转时，我们约定整个数组都处于「较大部分」。数组旋转以后，「较小部分」的数组一定严格小于（数组值互不相同）最左侧值，即「较大部分」的起始值。较大部分和较小部分内部元素都是严格递增的。
对于 target，我们要判断其位于哪一部分，据此我们决定二分的查找范围。我们可以以最左侧值 vL 为参照。若 target >= vL，则其位于左侧的「较大部分」，否则位于右侧「较小部分」，之后我们进行后续二分，与一般的二分没有区别。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int vL = nums[0];
        if (target == vL) {
            return 0;
        } else if (target > vL) {
            while (l <= r) {
                int mid = l + ((r - l) >> 2);
                int valM = nums[mid];
                if (valM == target) {
                    return mid;
                }
                if (valM >= vL) {
                    if (target > valM) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    r = mid - 1;
                }
            }
        } else {
            while (l <= r) {
                int mid = l + ((r - l) >> 2);
                int valM = nums[mid];
                if (valM == target) {
                    return mid;
                }
                if (valM < vL) {
                    if (target > valM) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }
}