二分查找

小米

2026-07-15 16:20:17

发布于：浙江

3阅读

0回复

0点赞

二分查找到底是个啥？
说白了就是在排好序的数组里快速找数。
怎么找呢？每次都看中间那个数，如果比目标小，那左边肯定都没戏了，直接扔掉左半边；如果比目标大，那右边全部pass。一次干掉一半，效率直接起飞。

时间复杂度 O(log n)，比从头到尾一个一个找（O(n)）快太多了。

核心思路（一定要刻在脑子里）
我习惯用闭区间 [left, right] 来想，这样最不容易乱：

left 指向数组开头，right 指向数组末尾。

循环条件 while (left <= right) —— 注意是 <=，不是 <，因为 left == right 的时候那个位置还没检查呢。

每次算 mid = left + (right - left) / 2（后面会讲为啥这么写）。

比较 nums[mid] 和 target：

相等 → 中了，返回下标。

nums[mid] < target → 目标在右边，left = mid + 1。

nums[mid] > target → 目标在左边，right = mid - 1。

循环结束了还没返回？那就是没找到，返回 -1。

最常用的模板（直接背这个）

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

两个经常用到的变体
有时候题目不只要找某个数，而是要找第一个出现的位置或者最后一个出现的位置，这时候就得改改逻辑了。

找左边界（第一个等于 target 的位置）

int leftBound(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 {  // 注意：>= target 的时候都往左缩，就是为了卡第一个
            right = mid - 1;
        }
    }
    // 退出时 left 指向第一个 >= target 的位置
    if (left >= nums.size() || nums[left] != target) return -1;
    return left;
}
找右边界（最后一个等于 target 的位置）

int rightBound(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 {  // <= target 的时候都往右缩，卡最后一个
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target) return -1;
    return right;
}