二分查找笔记(C++版)
一句话理解
> 二分查找:在一个排好序的数组里,每次取中间的数比较,根据大小关系砍掉一半范围,直到找到目标。
就像翻一本按拼音排序的字典找“中”字——翻到中间看到“妈”,知道“中”在后面,就只翻后半本,每次都能扔掉一半。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、什么是二分查找?
二分查找:在一个已经排好序的数组中,每次取中间的数比较,根据大小关系缩小查找范围。
核心思想:每次砍掉一半,剩下的范围越来越小
前提条件:数组必须是有序的(从小到大或从大到小)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、基础代码框架
运行示例:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、查找过程演示
在数组 [1, 3, 5, 7, 9, 11] 中查找 7:
只用了3次比较! 如果是普通查找,需要4次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、为什么用二分查找?
数据量 n 普通查找最多 二分查找最多 10 10次 4次 100 100次 7次 1000 1000次 10次 100万 100万次 20次 10亿 10亿次 30次
结论:数据量越大,二分查找的优势越明显。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、三种常见写法
写法1:查找某个数是否存在(返回下标)
写法2:查找第一个大于等于 TARGET 的位置(LOWER_BOUND)
写法3:查找最后一个小于等于 TARGET 的位置(UPPER_BOUND - 1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、经典题目
题目1:查找第一个大于等于X的位置(洛谷P2249)
题目描述:输入 n 个从小到大排好序的整数,进行 m 次询问。每次询问输入一个 x,输出 x 第一次出现的位置(从1开始),如果不存在输出 -1。
输入样例:
输出样例:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目2:数的范围
题目描述:输入 n 个从小到大排好序的整数,进行 m 次询问。每次询问输入一个 x,输出 x 第一次出现的位置和最后一次出现的位置(从1开始),如果不存在输出 -1 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、易错点
易错点 正确写法 mid 计算可能溢出 mid = left + (right - left) / 2 循环条件写错 找精确值用 while (left <= right) 边界更新少写 +1 或 -1 left = mid + 1,right = mid - 1 忘记排序 二分查找前必须先排序 数组下标从0还是1开始 统一习惯,注意边界
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、总结
要点 内容 核心思想 每次取中间,砍掉一半 前提条件 数据必须有序 时间复杂度 O(log n) 空间复杂度 O(1) 两种用法 在数组中找数 / 二分答案
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
记忆口诀
> 二分查找快又快,数据有序是前提
> 取个中间比一比,左移右移砍一半
> 百万数据二十次,这个效率真神奇
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------