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

二分查找是有序数组中的核心搜索算法，其本质是通过不断折半缩小搜索范围，直到找到目标元素。虽然最朴素的使用场景是在升序数组中查找指定值，但通过调整边界策略，它可以解决更复杂的问题，如查找区间、峰值元素等。

1. 基础二分查找

我们先从经典的 LeetCode 704 题入手，巩固最朴素的二分查找逻辑。

题目描述

给定一个升序数组 nums 和一个目标值 target，找出 target 在数组中的下标。如果不存在则返回 -1。

实现思路

初始化两个指针 left 和 right，分别指向数组首尾。计算中间位置 mid，比较 nums[mid] 与 target：

若 nums[mid] > target，说明目标在左半部分，将 right 移至 mid - 1。
若 nums[mid] < target，说明目标在右半部分，将 left 移至 mid + 1。
若相等，直接返回 mid。

循环终止条件为 left <= right。当 left > right 时仍未找到，说明目标不存在。

注意： 计算 mid 时，直接使用 (left + right) / 2 在数组极长时可能导致整数溢出。建议使用 left + (right - left) / 2 或 left + (right - left + 1) / 2 来避免此问题。

class Solution {
public:
    int search(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) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
};

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

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

核心差异

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

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