二分查找算法详解与实战模板

2. 查找左右边界的二分查找

当需要查找目标值的第一个或最后一个位置（例如 LeetCode 34 题）时，朴素二分查找可能无法直接满足要求，或者效率不够高。此时需要明确区分查找左边界和右边界的模板。

核心差异

1. 循环条件：通常使用 left < right。当 left == right 时，指针已收敛到唯一候选位置，无需继续判断。
2. Mid 计算：
   • 查找左边界时，若 mid 偏大导致死循环，需向下取整：mid = left + (right - left) / 2。
   • 查找右边界时，若 mid 偏小导致死循环，需向上取整：mid = left + (right - left + 1) / 2。
3. 更新策略：
   • 找左边界：若 nums[mid] >= target，则 right = mid；否则 left = mid + 1。
   • 找右边界：若 nums[mid] <= target，则 left = mid；否则 right = mid - 1。

代码实现

以下代码同时实现了查找左端点和右端点的逻辑，并处理了目标值不存在的情况。

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 begin = left;

        // 查找右端点
        left = 0; right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        int end = left;

        // 验证是否真的存在 target
        if (begin < nums.size() && nums[begin] == target) {
            return {begin, end};
        }
        return {-1, -1};
    }
};

经验总结：不要死记硬背模板。关键在于分析题意，确定搜索区间的二段性。记住一点：当 if...else 分支中出现 mid - 1 时，mid 的计算通常需要向上取整以防死循环。

3. 实战演练

通过几道经典题目进一步巩固二分查找的应用。

3.1 搜索插入位置 (LeetCode 35)

需求：在有序数组中找到目标值下标，若不存在则返回应插入的位置以保持有序。 思路：本质上仍是查找左边界。若最终 target 大于数组末尾元素，则插入位置为 left + 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[left]) return left + 1;
        return left;
    }
};

3.2 x 的平方根 (LeetCode 69)

需求：计算非负整数 x 的算术平方根的整数部分。 思路：寻找最大的 k 使得 k * k <= x。这属于查找右边界问题。注意 mid * mid 可能溢出，需使用 long long。

class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        int left = 1, right = x;
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }
};

3.3 山脉数组的峰顶索引 (LeetCode 852)

需求：在山脉数组中找到峰值元素的索引。 思路：数组先增后减，具有二段性。若 arr[mid] < arr[mid + 1]，说明处于上升坡，峰值在右侧；反之在左侧。

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

3.4 旋转排序数组中的最小值 (LeetCode 153)

需求：在旋转后的升序数组中找到最小值。 思路：利用数组后半段小于等于前半段的特性。若 nums[mid] > nums[n - 1]，说明最小值在右侧；否则在左侧（含 mid）。

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

3.5 0〜n-1 中缺失的数字

需求：在长度为 n 的递增数组中找出缺失的一个数字。 思路：若 nums[i] == i，说明缺失数字在右侧；否则在左侧。这是典型的查找左边界变体。

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[left] == left) left++;
        return left;
    }
};

掌握二分查找的关键在于识别问题的二段性，并根据具体需求选择合适的边界收缩策略。多练习不同变体，能显著提升对算法边界的敏感度。