二分查找算法详解与实战题解

寻找右边界： 目标是找到最后一个等于 target 的位置。将区间分为：小于等于 target 的左侧，大于 target 的右侧。当 nums[mid] <= target 时，mid 可能是结果或结果在右侧，故 left = mid；否则 right = mid - 1。此处 mid 需向上取整（即 +1），防止 left 原地踏步。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int begin = 0, 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};
        begin = left;
        // 找右边界
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {begin, right};
    }
};

3. 搜索插入位置

思路解析： 本质仍是寻找满足特定条件的最小索引。若 nums[mid] >= target，则 mid 及其左侧可能为插入点，收缩右边界 right = mid；若 nums[mid] < target，则插入点在右侧，left = mid + 1。循环结束时 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] 分为两段：平方后小于等于 x 的左侧，大于 x 的右侧。使用二分查找最大的满足 mid * mid <= x 的数。注意乘法运算需使用 long long 防止溢出。

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

5. 山脉数组的峰顶索引

思路解析： 山脉数组先增后减。比较 arr[mid] 与 arr[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，若 nums[i] < nums[i+1]，说明右侧存在上升趋势，峰值必在右侧；反之则在左侧。利用这一二段性，可快速收敛至任意一个峰值。

class Solution {
public:
    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. 寻找旋转排序数组中的最小值

思路解析： 旋转数组由两个有序子数组组成。最小值位于第二个子数组的首部。通过与右端点 nums[right] 比较 nums[mid] 来判断 mid 落在哪个区间：若 nums[mid] > nums[right]，说明最小值在右侧，left = mid + 1；否则在左侧，right = mid。

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

8. 点名（缺失数字）

思路解析： 在升序数组中，若未缺失数字，则 nums[i] == i。一旦缺失，后续所有元素均满足 nums[i] > i。利用此二段性，当 nums[mid] == mid 时，缺失点在右侧，left = mid + 1；否则在左侧，right = mid。最终 left 即为缺失数字。

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;
        }
        return left == records[left] ? left + 1 : left;
    }
};

总结

二分查找的关键不在于背诵模板，而在于理解如何根据题意构造'二段性'。确定好划分标准后，指针的移动方向自然清晰。实际编码时，务必注意边界条件（如空数组）、整数溢出及死循环风险（特别是 mid 的取整方式）。