二分查找算法经典例题与模板总结

2.1 算法原理

由于该题给定数组要么是递增要么不变，可以用一个值划分两个区间，所以具有二段性，符合使用二分算法的条件。

查找区间左端点

与上题总结的朴素模板相比，该题的判断条件要发生变化。根据举例找出一般规律：

1. 当 x 小于 target(t) 的时候，由于我们寻找左端点，并且 mid 下标对应的值就是 x，那么区间 [left, mid] 中的值都小于 t，可以全部舍弃，将 left 更新到 mid+1 下标处。
2. 为什么要将 > 和 = 条件放在一起分析？因为 = 时只是代表有可能找到了左端点，该题并未结束，不能作为结束条件返回结果，所以一起分析因为该区间包含了左端点。
3. 当 x >= t 时，由于 mid 位置有可能是左端点下标所以不能舍去，左端点一定在区间 [left, mid] 中，将 right 更新为 mid。

• 细节处理
  1. 循环条件的判断

     循环条件为 left < right：数组内元素总共三种情况，存在左端点、元素全部小于目标值、全部大于目标值，当 left == right 时就是最终结果，无需判断。如果判断当数组内元素全部小于目标值时 left = mid+1 刚好结束循环，但若元素大于等于目标值时 right = mid 会陷入死循环。

  2. 求中点的操作

     1 式在 x < t 时 left = mid+1 移动到 right 处结束循环，当 x >= t 时 right = mid 移动到 left 处结束循环。 2 式在 x < t 时 left = mid+1 移动到 right+1 处结束循环，但 x >= t 时 right = mid 位置不变会陷入死循环。

查找区间右端点

同理通过分析例子得出一般规律：

1. 当 x <= t 时，区间 [left, mid-1] 可以舍弃掉，mid 处有可能就是右端点，所以令 left = mid，继续寻找。
2. 当 x > t 时，区间 [mid, right] 可以舍弃掉因为都大于右端点值，令 right = mid-1，继续寻找。

• 细节处理
  1. 循环条件

     与寻找左端点相同，都是 left < right。

  2. 求中点方式

     分析过程与求左端点思路相同，无非是当元素为偶数个时中间点有两个，取左还是右，当其中一个在 x <= t 条件下 left == mid 下标都未发生变化因此会陷入死循环，不再赘述。

2.2 总结模板

画星部分不用特意去记，根据题意分析二段性就可以得出，求中间值的方法可以这么想，当求左端点时，当数组元素为偶数个数时中间值有两个，mid 落在左边那个，对应的计算方法就不要 +1，反之求右端点时 mid 落在中间值右边那个，计算方法要 +1，循环判断条件都相同。 更万能的记忆的方法，当 if 条件语句中出现了减法，那么中间值的计算就要 +1。

2.3 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 判断数组为空的情况
        if (nums.size() == 0) return {-1, -1};
        // 判断数组是否具有 target 元素
        int n = 0;
        for (auto e : nums)
            if (e == target) n++;
        if (n == 0) return {-1, -1};
        
        // 查找左端点
        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;
        }
        
        // 查找右端点
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int m = l + (r - l + 1) / 2;
            if (nums[m] <= target) l = m;
            else r = m - 1;
        }
        return {left, r}; // 最后写左右都可以，它们最终会相遇
    }
};

3. LeetCode 20 x 的平方根

3.1 算法原理

1. 暴力解法

   依次枚举所有数的平方，枚举区间为整个数组不需要额外判断，当等于目标值时直接返回，大于时说明前一个为结果。需注意由于是相乘，有可能超过 int 的最大值，应该使用 long long 类型。

class Solution {
public:
    int mySqrt(int x) {
        // 由于两个较大的数相乘可能会超过 int 最大范围
        // 因此用 long long
        long long i = 0;
        for (i = 0; i <= x; i++) {
            // 如果两个数相乘正好等于 x，直接返回 i
            if (i * i == x) return i;
            // 如果第一次出现两个数相乘大于 x，说明结果是前一个数
            if (i * i > x) return i - 1;
        }
        // 为了处理 oj 题需要控制所有路径都有返回值
        return -1;
    }
};

2. 二分算法

   可以根据目标值来划分区间，具有二段性。[0, ret] 之间的元素，平方之后都是小于等于 x 的，ret 可能为目标值，令 left = ret；[ret + 1, x] 之间的元素，平方之后都是大于 x 的，令 right = ret-1。 如果按小于 x 和大于等于 x 的区间来划分同理，分别令 left = mid+1 和 right = mid 即可。

class Solution {
public:
    int mySqrt(int x) {
        if (x < 1) return 0; // 处理边界情况
        int left = 1, right = x;
        while (left < right) {
            long long mid = left + (right - left + 1) / 2; // 防溢出
            if (mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

4. LeetCode 35 搜索插入位置

4.1 算法原理

设插入位置为 ret，根据题意分析二段性可划分为小于目标值 t 和大于等于 t 的区域，左右指针的移动情况如下，当 mid 落在 [left, ret-1] 区域时由于全部小于 t，令 left = mid+1；当 mid 落在 [ret, right] 中时由于 ret 可能为目标值所以令 right = mid。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        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 (target > nums[right]) return right + 1;
        return left; // 由于左右指针已经相遇，返回谁都可以
    }
};

5. LeetCode 852 山脉数组的峰顶索引

5.1 算法原理

• 1. 暴力解法

  峰顶的特点：比两侧的元素都要大。因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。

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;
        // 为了处理 oj 需要控制所有路径都有返回值
        return -1;
    }
};

• 2. 二分查找

  虽然该题数组不有序，但具有二段性，山峰左右两边都小于山峰值，中间位置 mid 可以分为以下两种种情况：

1. 用索引 mid 和 mid-1 进行比较

   峰值 mid 一定得放到左边区间中，因为是和前一个元素作比较，左区间中的最后一个元素可能位峰值，若放到右边区间中更新索引时峰值可能会被跳过，mid 的计算要 +1。

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;
    }
};

2. 用索引 mid 和 mid+1 作比较

   此时将峰值放到右边区间，右边区间的第一个元素可能为峰值，更新时 right = mid，left = mid+1，此时 mid 的计算不 +1。

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

6. LeetCode 153 寻找旋转排序数组中的最小值

6.1 算法原理

由题意得数组升序，旋转后具有两段性。 旋转后的数据分为这样两段，C 点即为所求最小值。我们以 D 点作为划分值。 当 mid 落在 AB 区间时不满足，left = mid+1 要跳出该区间；落在 CD 区间时 mid <= 最小值，为了缩小搜寻范围令 right = mid。

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

7. LeetCode 173 点名

7.1 算法原理

二分查找

由题意得数组递增且有序，中间会少一个数，这个数就可以把数组划分为两个区间。 前区间元素值对应索引，后区间元素对应索引 +1，我们要求的就是后区间的第一个元素。

细节问题：

若数组未被划分为两个区间，每个元素都等于其索引，那缺失值超出数组索引有效范围，返回最后索引 +1。

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 (records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        // 完全连续的特殊情况判断
        if (records[right] == right) return right + 1;
        else return right;
    }
};

除此之外还可以尝试：

1. 哈希表
2. 直接遍历找结果
3. 位运算
4. 数学 (高斯求和公式) 这些方法的时间复杂度都为 O(n)，不如二分。