二分查找经典例题解析与模板总结

查找右端点

当 mid 对应的值小于等于目标值时，mid 可能是右端点，更新 left = mid。当 mid 大于目标值时，更新 right = mid - 1。

细节处理：

1. 中点计算：求右端点时，为避免死循环，mid 计算需要加 1，即 left + (right - left + 1) / 2。

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;
        }
        
        // 查找右端点
        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;
        }
        
        // 验证是否存在
        if (nums[left] != target) return {-1, -1};
        return {left, r};
    }
};

3. 求平方根（LeetCode 69）

暴力解法

枚举区间，注意乘法可能溢出，需使用 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）

核心思路

寻找第一个大于等于目标值的索引。若目标值大于所有元素，返回末尾索引 +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 与相邻元素即可确定峰值方向。

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）

核心思路

旋转后的数组分为两段升序序列。比较 mid 与末尾元素 nums[n]，判断最小值在哪一侧。

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。目标是找到后区间的第一个元素。

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

以上总结了二分查找在不同场景下的变体。核心在于识别'二段性'，并根据边界收缩的方向调整 mid 的计算方式与循环条件。实际编码时，务必注意整数溢出与边界条件的处理。