二分查找算法详解与模板总结：从原理到变体

时间复杂度分析

• 时间复杂度：O(log n)
  • 每次比较后，搜索范围减半
  • 对于大小为 n 的数组，最多需要 log₂(n) 次比较
• 空间复杂度：O(1)
  • 只需要常数级别的额外空间

二分查找的变体

1. 查找第一个等于目标的位置

int findFirst(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid; // 记录当前位置
            right = mid - 1; // 继续向左查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

2. 查找最后一个等于目标的位置

int findLast(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            result = mid; // 记录当前位置
            left = mid + 1; // 继续向右查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

3. 查找第一个大于等于目标的位置

int findFirstGreaterOrEqual(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 {
            left = mid + 1; // 当前太小，向右找
        }
    }
    return left; // left 就是第一个 >= target 的位置
}

常见应用场景

1. 有序数组的查找 - 最基础的应用
2. 求平方根 - 在 0 到 x 之间二分查找
3. 旋转数组的查找 - 如 [4,5,6,7,0,1,2] 中查找
4. 寻找峰值 - 在山峰数组中找到最大值
5. 在答案空间二分 - 如"找到最小速度使得在规定时间内完成任务"

注意事项和常见错误

1. 循环条件：left <= right vs left < right 的选择
2. 边界更新：left = mid + 1 和 right = mid - 1 要正确
3. 整数溢出：使用 mid = left + (right - left) / 2 而非 (left + right) / 2
4. 数组必须有序：二分查找的前提是有序，否则结果错误
5. 重复元素：处理重复元素时要明确需求（找第一个/最后一个）

二分查找虽然原理简单，但细节容易出错。建议多练习不同类型的题目，熟练掌握各种变体的写法。

二分算法模板总结

// 找左边
while (left < right) {
    int mid = left + (right - left) / 2;
    // 左边
    if (nums[mid] >= target) right = mid;
    // 右边
    else left = mid + 1;
}

// 找右边
while (left < right) {
    int mid = left + (right - left + 1) / 2;
    // 右边
    if (nums[mid] <= target) left = mid;
    // 左边
    else right = mid - 1;
}

实战练习题目（含链接）

二分查找（easy）
在排序数组中查找元素的第一个和最后一个位置（medium）
搜索插入位置（easy）
x 的平方根（easy）
山峰数组的峰顶（easy）
寻找峰值（medium）
搜索旋转排序数组中的最小值（medium）
0〜n-1 中缺失的数字（easy）