二分查找算法原理及常见变种解析

二、简单的二分查找

题目链接：https://leetcode.cn/problems/binary-search

算法解析：这题大家套'二分算法原理剖析'的第一套模板即可。

三、找目标范围

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

算法解析：暴力解法是遍历数组，找先目标值，再看是否有连续的目标值，记录它们的下标即可。

算法解析（以下是找的到 target 的情况，需要判断找不到的情况）： 首先找左端点：以上图为例，具备完美的边界（二段性），左边界的 8 比左边的 0,3,5,6 都要大，如果 mid 落在边界左边，不管怎样都要找比 mid 位置大的数，所以如果小于目标值，left = mid + 1。 那么如果 mid 落在>=8（左边界的 8）的位置，right 不应该跳过且收缩，所以 right = mid。 其次是右端点：以上图为例，具备完美的边界（二段性），同理： 如果落在最右边 8 的左边，那么 left 不能跳过这段区间，只能是 left = mid，不断收缩。 如果落在最右边 8 的右边，那么 right 最终肯定要跳过才行，所以 right = mid - 1，跳过 + 收缩。

代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1, -1};
        vector<int> V;
        int left = 0, right = nums.size() - 1;
        int mid = 0;
        //找左端点
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else if(nums[mid] < target) left = mid + 1;
        }
        if(nums[left] == target) {
            V.push_back(left);
        } else {//如果找不到
            V.push_back(-1);
        }
        //找右端点
        left = 0, right = nums.size() - 1;
        while(left < right) {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else if(nums[mid] <= target) left = mid;
        }
        if(nums[left] == target) {
            V.push_back(left);
        } else {//如果找不到
            V.push_back(-1);
        }
        return V;
    }
};

四、搜索插入位置

题目链接：https://leetcode.cn/problems/search-insert-position

算法解析：对于有二段线的数组 + 目标值的，我们采用二分的方法，下面是思路，采用第几套模板： 我们观察这两组值： nums = [1,3,5,6], target = 2 nums = [1,3,5,6], target = 7 可以看到：找的都是稍大的位置，比如第一组目标位置是 1 号下标，那么如果 nums[i]<2，有没有可能？完全没有，所以如果算出的目标值比小，那么 left = mid + 1，只要确定了一边，那么另一边就出来了，right = mid，循环条件是 left < right，最后肯定是 left 和 right 相遇出循环，此时判断是不是目标值，再做返回值处理。

代码：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid = 0;
        //找左端点
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else if(nums[mid] < target) left = mid + 1;
        }
        if(nums[left] < target) return left + 1;
        return left;
    }
};

五、寻找旋转数组中的最小值

题目链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array

算法解析：对于数组中找值的这类题目，我们先看有没有二段性，很明显有：数组中最小的元素。 每旋转一次是把最后一个值拿到前面来，因此，就像一个蜿蜒的山峰。 因此可以以 nums[0] 和 nums[size-1] 来作为基准值：以 nums[0] 为例： 如果比 nums[0] 大，说明在数组第二象限，left = mid + 1（因为不可能在这段区间），反之如果<它，那么可能在第四象限，就需要缩小区间，right = mid，切记不能跳过 mid，最后处理边界情况： 如果 left 一直满足 left = mid + 1，出循环也就是 left == nums.size()，比如 0,1,2,3,4，即 left=right 的时候。

代码：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size();
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[0]) left = mid + 1;
            else right = mid;
        }
        return left == nums.size() ? nums[0] : nums[left];
    }
};