深高北-二分思想——二分查找

张kk

2026-06-26 15:41:25

发布于：广东

8阅读

0回复

0点赞

二分查找笔记（C++版）

一句话理解

二分查找：在一个排好序的数组里，每次取中间的数比较，根据大小关系砍掉一半范围，直到找到目标。

就像翻一本按拼音排序的字典找“中”字——翻到中间看到“妈”，知道“中”在后面，就只翻后半本，每次都能扔掉一半。

一、什么是二分查找？

二分查找：在一个已经排好序的数组中，每次取中间的数比较，根据大小关系缩小查找范围。

核心思想：每次砍掉一半，剩下的范围越来越小

前提条件：数组必须是有序的（从小到大或从大到小）

二、基础代码框架

#include <iostream>
using namespace std;

int a[100010];

int main() {
    int n, target;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> target;
    
    int left = 1;
    int right = n;
    int pos = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        
        if (a[mid] == target) {
            pos = mid;
            break;
        } else if (a[mid] < target) {
            left = mid + 1;   // 目标在右边，砍掉左边
        } else {
            right = mid - 1;  // 目标在左边，砍掉右边
        }
    }
    
    if (pos != -1) {
        cout << "找到了，下标是：" << pos << endl;
    } else {
        cout << "没找到" << endl;
    }
    
    return 0;
}

运行示例：

6
1 3 5 7 9 11
7
找到了，下标是：4

三、查找过程演示

在数组 [1, 3, 5, 7, 9, 11] 中查找 7：

第1步：left=1, right=6, mid=(1+6)/2=3
       a[3]=5，5 < 7，所以 left = 4
       范围变成：[7, 9, 11]

第2步：left=4, right=6, mid=(4+6)/2=5
       a[5]=9，9 > 7，所以 right = 4
       范围变成：[7]

第3步：left=4, right=4, mid=4
       a[4]=7，找到了！

只用了3次比较！ 如果是普通查找，需要4次。

四、为什么用二分查找？

数据量 n	普通查找最多	二分查找最多
10	10次	4次
100	100次	7次
1000	1000次	10次
100万	100万次	20次
10亿	10亿次	30次

结论：数据量越大，二分查找的优势越明显。

五、三种常见写法

写法1：查找某个数是否存在（返回下标）

int binarySearch(int a[], int n, int target) {
    int left = 1, right = n;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;  // 没找到
}

写法2：查找第一个大于等于 target 的位置（lower_bound）

int lowerBound(int a[], int n, int target) {
    int left = 1, right = n;
    int ans = n + 1;  // 如果全小于target，返回 n+1
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (a[mid] >= target) {
            ans = mid;
            right = mid - 1;  // 继续往左找
        } else {
            left = mid + 1;
        }
    }
    
    return ans;
}

写法3：查找最后一个小于等于 target 的位置（upper_bound - 1）

int upperBound(int a[], int n, int target) {
    int left = 1, right = n;
    int ans = 0;  // 如果全大于target，返回 0
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (a[mid] <= target) {
            ans = mid;
            left = mid + 1;  // 继续往右找
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
}

六、经典题目

题目1：查找第一个大于等于x的位置（洛谷P2249）

题目描述：输入 n 个从小到大排好序的整数，进行 m 次询问。每次询问输入一个 x，输出 x 第一次出现的位置（从1开始），如果不存在输出 -1。

输入样例：

8 3
1 2 2 2 3 4 5 6
2
3
7

输出样例：

2
5
-1

#include <iostream>
using namespace std;

int a[1000010];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    while (m--) {
        int x;
        cin >> x;
        
        int left = 1, right = n;
        int ans = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (a[mid] >= x) {
                if (a[mid] == x) ans = mid;
                right = mid - 1;  // 继续往左找
            } else {
                left = mid + 1;
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

题目2：数的范围

题目描述：输入 n 个从小到大排好序的整数，进行 m 次询问。每次询问输入一个 x，输出 x 第一次出现的位置和最后一次出现的位置（从1开始），如果不存在输出 -1 -1。

#include <iostream>
using namespace std;

int a[1000010];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    while (m--) {
        int x;
        cin >> x;
        
        // 找第一次出现
        int left = 1, right = n;
        int first = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] >= x) {
                if (a[mid] == x) first = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // 找最后一次出现
        left = 1, right = n;
        int last = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] <= x) {
                if (a[mid] == x) last = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        cout << first << " " << last << endl;
    }
    
    return 0;
}

七、易错点

易错点	正确写法
mid 计算可能溢出	`mid = left + (right - left) / 2`
循环条件写错	找精确值用 `while (left <= right)`
边界更新少写 +1 或 -1	`left = mid + 1`，`right = mid - 1`
忘记排序	二分查找前必须先排序
数组下标从0还是1开始	统一习惯，注意边界

八、总结

要点	内容
核心思想	每次取中间，砍掉一半
前提条件	数据必须有序
时间复杂度	O(log n)
空间复杂度	O(1)
两种用法	在数组中找数 / 二分答案