二分查找算法实战：7 道经典题目详解

查找右端点

• 逻辑：当 x <= target 时，保留 [mid, right]，更新 left = mid；当 x > target 时，舍弃 [mid, right]，更新 right = mid - 1。
• 细节：
  1. 循环条件同样为 left < right。
  2. 中点计算需加 1 (mid = left + (right - left + 1) / 2)，否则当 left == mid 时会陷入死循环。

代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) 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;
        }
        
        // 检查是否找到
        if (nums[left] != target) return {-1, -1};
        
        // 查找右端点
        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 69)

算法原理

暴力枚举需遍历至 x，且 i * i 可能溢出 int 范围，建议使用 long long。二分法更具优势，根据目标值划分区间：[0, ret] 平方后小于等于 x，[ret+1, x] 平方后大于 x。

代码实现

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)

算法原理

设插入位置为 ret。小于目标值的区域令 left = mid + 1，大于等于目标值的区域令 right = mid。若目标值大于数组最大值，返回 right + 1。

代码实现

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)

算法原理

虽数组整体无序，但具备二段性：峰值左侧递增，右侧递减。

• 方法一：比较 mid 与 mid-1。若 arr[mid] > arr[mid-1]，说明处于上升段，峰值在右侧（含 mid），left = mid，中点计算需加 1。
• 方法二：比较 mid 与 mid+1。若 arr[mid+1] > arr[mid]，说明处于上升段，left = mid + 1，中点计算不加 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;
    }
};

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

算法原理

升序数组旋转后仍具二段性。以最后一个元素 nums[n] 为基准：

• 若 mid > nums[n]，说明最小值在右侧，left = mid + 1。
• 若 mid <= nums[n]，说明最小值在左侧（含 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;
            else right = mid;
        }
        return nums[right];
    }
};

7. 点名问题 (缺失索引检测)

算法原理

数组递增且有序，中间缺失一个数。前区间元素值等于索引，后区间元素值等于索引 +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;
        return right;
    }
};

注：此类问题也可用哈希表、遍历、位运算或数学公式解决，但时间复杂度均为 O(n)，二分查找的 O(logn) 更优。