二分查找算法核心逻辑与实战题解

关于 mid 的落点，分为两种情况：

• 当 mid 落在 [left, resLeft-1] 区间时，即 arr[mid] < target。说明 [left, mid] 都可以舍去，此时更新 left 到 mid+1 的位置，继续在 [mid+1, right] 上寻找左边界；
• 当 mid 落在 [resLeft, right] 区间时，也就是 arr[mid] >= target。说明 [mid+1, right]（因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界。

注意：这里找中间元素需要向下取整。 因为后续移动左右指针时：

• 左指针：left = mid + 1，是会向后移动的，因此区间数会缩小；
• 右指针：right = mid，可能会原地踏步（如：若向上取整，如果剩下两个元素，left==1，right==2，mid==2。更新区间后，left、right、mid 的值没有改变，就会陷入死循环）。 因此一定要注意，当 right == mid 时，要向下取整。

寻找右边界思路

用 resRight 表示右边界，其特点如下：

• 左边区间（包括右边界）[left, resRight] 都是小于等于 x 的；
• 右边区间 [resRight+1, right] 都是大于 x 的。

关于 mid 的落点，分为下面两种情况：

• 当 mid 落在 [left, resRight] 区间时，说明 [left, mid-1]（mid 不可以舍去，因为可能是最终结果）都是可以舍去的，此时更新 left 到 mid 的位置；
• 当 mid 落在 [resRight+1, right] 的区间的时候，说明 [mid, resRight] 内元素是可以舍去的，此时更新 right 到 mid-1 位置。

注意：这里找中间元素需要向上取整。 因为后续移动左右指针的时候：

• 左指针：left = mid，可能会原地踏步（如：若向下取整，如果剩下 1、2 两个元素，left==1，right==2，mid==1。更新区间之后，left、right、mid 的值没有改变，就会陷入死循环）。
• 右指针：right = mid - 1，是会向前移动的，因此区间是会缩小的； 因此一定要注意，当 right = mid - 1 时，要向上取整。

二分查找算法总结

1. 关于什么时候用三段式，还是二段式中的某一个，一定不要强行去用，而是通过具体的问题分析情况，根据查找区间的变化确定指针的转移过程，从而选择一个模板。
2. 当选择两段式的模板时：
   • 在求 mid 时，只有 right-1 的情况下，才会向上取整（即 +1，取中间数时）。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 数组为空时
        if (nums.size() == 0) return {-1, -1};
        
        int begin = 0;
        int left = 0, right = nums.size() - 1;
        
        // 求区间左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] != target) return {-1, -1};
        else begin = left;
        
        // 求区间右端点
        left = 0, right = nums.size() - 1;
        // left 没必要重新置为 0，因为它查找左端点后，一定不会超过右端点
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return {begin, right};
    }
};

3. 搜索插入位置

算法思路

a. 分析插入位置左右两侧区间上元素的特点： 设插入位置的坐标为 index，根据插入位置的特点可以知道：

• [left, index-1] 内的所有元素均是小于 target 的；
• [index, right] 内的所有元素均是大于等于 target 的。

b. 设 left 为本轮查询的左边界，right 为本轮查询的右边界。根据 mid 位置元素的信息，分析下一轮查询的区间：

• 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [left, mid] 上。因此，更新 right 到 mid 位置，继续查找。
• 当 nums[mid] < target 时，说明 mid 落在了 [left, index-1] 区间上，mid 右边但不包括 mid 本身，可能是最终结果，索引我们接下来查找的区间 [mid+1, right] 上。因此，更新 left 到 mid+1 位置，继续查找。

c. 直到我们的查找区间长度变为 1，即 left == right 时，left 或 right 所在的位置就是我们要找的结果。

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

4. x 的平方根

算法思路一（暴力） 依次枚举 [0, x] 之间的所有数 i：（这里没有必要研究是否枚举到 x/2 还是 x/2+1。因为我们找到结果之后直接就返回了，往后的情况就不会再判断。反而研究枚举空间，既耽误时间，又可能出错）

• 若 i*i == x，直接返回 x；
• 若 i*i > x，说明之前的一个数是结果，返回 i-1。

由于 i*i 可能超过 int 的最大值，因此使用 long long 类型。

class Solution {
public:
    int mySqrt(int x) {
        // 防止溢出
        long long i = 0;
        for (i = 0; i <= x; i++) {
            if (i * i == x) return i;
            if (i * i > x) return i - 1;
        }
        return -1;
    }
};

算法思路二（二分） 设 x 的平方根的最终结果为 index： a. 分析 index 左右两次数据的特点：

• [0, index] 之间的元素平方后都是小于等于 x 的；
• [index+1, x] 之间的元素，平方后都是大于 x 的。 由此可以使用二分查找算法。

class Solution {
public:
    int mySqrt(int x) {
        // 可将区间分为小于等于 x 的 大于 x 的
        int left = 1, right = x;
        if (x < 1) return 0;
        while (left < right) {
            // long long 防止溢出
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

5. 山脉数组的峰顶索引

算法思路一（暴力） 顶峰的特点：比两边的元素都要大。因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int n = arr.size();
        // 遍历数组内每一个元素，直到找到峰顶
        for (int i = 1; i < n - 1; i++) {
            // 峰顶满足条件
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return i;
        }
        return -1;
    }
};

算法思路二（二分）

1. 分析峰顶位置的数据特点，以及山峰两旁的数据的特点：

• 峰顶数据特点：arr[i] > arr[i-1] && arr[i] > arr[i+1]；
• 峰顶左边的数据特点：arr[i] > arr[i-1] && arr[i] < arr[i+1]，即呈上升趋势；
• 峰顶右边数据的特点：arr[i] < arr[i-1] && arr[i] > arr[i+1]，即呈下降趋势。

2. 因此，根据 mid 位置的信息，我们可以分为下面三种情况：

• 若 mid 位置呈上升趋势，说明我们接下来要在 [mid+1, right] 区间继续搜索；
• 若 mid 位置呈下降趋势，说明我们接下来要在 [left, mid-1] 区间搜索；
• 若 mid 位置就是山峰，直接返回结果。

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        // 峰顶一定不会位于首尾
        int left = 1, right = arr.size() - 2;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

6. 寻找峰值

解法思路（二分） 寻找二段性：任取一点 i，与下一个点 i+1，会有如下两种情况：

• arr[i] > arr[i+1]：此时【左侧区域】一定会存在山峰（因为最左侧是负无穷），那么我们可以取左侧寻找结果；
• arr[i] < arr[i+1]：此时【右侧区域】一定会存在山峰（因为最右侧是负无穷），那么我们可以取右侧寻找结果。

当我们找到【二段性】时，就可以尝试用【二分查找】算法解决问题。

class Solution {
public:
    // 3 种情况，1 一直递减；2 一直递增；3 有增有减
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 左边一定存在峰值，右边不一定 [左边] [右边]
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

7. 寻找旋转排序数组中的最小值

算法思路（二分）

c 点就是我们要求的点。

二分的本质：找到一个判断标准，使得查找区间能够一分为二。

通过图像我们可以发现，【A，B】区间内的点都是严格大于 D 点的值的，C 点的值是严格小于 D 的点的值的。但是当【C，D】区间只有一个元素的时候，C 点的值是可能等于 D 点的值的。

因此，初始化左右两个指针 left，right： 然后根据 mid 的落点，我们可以这样划分下一次查询的区间：

• 当 mid 在【A，B】区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在【mid+1，right】上；
• 当 mid 在【C，D】区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间在【left，mid】上。

当区间长度变成 1 的时候，就是我们要找的结果。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int x = nums[right];
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 与数组中最后一个值比较
            if (nums[mid] > x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

也可以用左侧为基准值，但要注意排除数组为升序的情况：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int x = nums[left]; // 以左端点为基准值
        if (x < nums[right]) return nums[left];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= x) {
                left = mid + 1; // 此时左端点一定不是最小值
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

8. 点名

算法思路（二分） 在这个升序的数组中，我们发现：

• 在第一个缺失位置的左边，数组内的元素都是与数组的下标相等的；
• 在第一个缺失位置的右边，数组内的元素与数组下标是不相等的。

因此，我们可以利用这个【二段性】，来使用【二分查找】算法。

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid == records[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 防止缺失的是最后一个数字
        if (left == records[left]) return left + 1;
        return left;
    }
};