二分法。 二分法的本质、模板、例题 – 知乎

二分法的关键是找出目标点的性质。

观察题目中，旋转数组的性质，能发现最小的数字一定是小于等于最右端点的。即找出某区间的最左值，用二分法的右区间模板。

class Solution {
public:
    int minArray(vector<int> &numbers) {
        int pivot = numbers.back();
        int l = 0, r = numbers.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (numbers[mid] <= pivot) r = mid;//考虑到可能只旋转了一个数，最小值就是最后一个，故小于等于
            else l = mid + 1;
        }
        return numbers[l];
    }
};

上述方法无法解决重复数字的问题。

• pivot 取的是数组最后一个元素 numbers.back()，且视为 numbers[mid] <= pivot 时，最小值在 [l, mid] 区间。
• 但旋转数组可能有重复元素（如 [1,1,1,0,1]），此时 numbers[mid] == pivot 并不能保证最小值在 [l, mid]，可能仍在右侧。

解决的方法很简单：l从第一个非重复元素开始

class Solution {
public:
    int minArray(vector<int> &numbers) {
        //3 4 1 2 3
        int l = 0, r = numbers.size() - 1;
        int pivot = numbers.back();
        while(l < numbers.size() - 1 && numbers[l] == pivot) l++; //上一版代码的补丁，从第一个不同的数字开始。
        if(numbers[l] <= pivot) return numbers[l]; //特判
        while (l < r) {
            int mid = l + r >> 1;
            if (numbers[mid] <= pivot) r = mid;
            else l = mid + 1;
        }
        return numbers[l];
    }
};

另注：二分法有两个模板。

右区间模板：
得到右区间的左端点。
	int search(vector<int> &nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return -1;
        return l;
    }

左区间模板：
得到左区间的右端点。 
int search(vector<int> &nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        if (nums[l] != target) return -1;
        return l;
    }
};