◎学完你会
- 写一个在有序数组里找目标的二分查找，理解
l/r/mid 三根指针如何收缩区间；
- 知道为什么二分是 O(log n)——每次砍一半，规模翻倍只多一步；
- 避开边界取整与死循环这两个最常见的二分坑。
1动一动：看二分怎么砍区间
有序数组 [1,3,5,7,9,11,15,19]。设一个目标 t，每点一次「走一步」，
l（黄）和 r（蓝）就把范围砍半，直到 mid 命中（绿）。
目标 t =
初始 l=0, r=7。点「走一步」开始二分。
2关键命令：最朴素的二分
int l=0, r=n-1;
while (l <= r) {
int mid = (l + r) / 2; // 注意别写 l+r 溢出
if (a[mid] == t) return mid; // 命中
if (a[mid] < t) l = mid + 1; // 目标在右半边
else r = mid - 1; // 目标在左半边
}
为什么 O(log n)：每走一步，能搜的范围减半。8 个元素 → 3 步；100 万 → 20 步；10 亿 → 30 步。规模翻十倍，步数几乎不变。
前提是有序：二分靠“中点两侧哪边更可能”来决定方向，乱序数组根本没这个信息，二分退化成瞎猜。
⚠易错点
mid=(l+r)/2 整型溢出：当 l、r 都是接近 int 上限的大数，l+r 会溢出成负数。稳妥写法 mid = l + (r-l)/2。
死循环：若写成 l = mid; r = mid 且 mid 向下取整，区间可能永远不变。收缩必须保证 每次 l 或 r 都真变小。
while(l<r) 与 while(l<=r) 混用：两种写法退出条件不同，收缩方式也不同，别换来换去。
没检查数组越界：找不到时函数要返回“不存在”（如 -1），别返回一个假下标。
?跨学科：二分查找就是“折半排除”
你猜一个 1~100 的数，对方只说“大了/小了”——最聪明的猜法就是每次取中点，最多 7 次必中。这比从 1 到 100 挨个问快得多，正是二分：每次利用有序性砍掉一半不可能。
文献检索、词典查词、数据库索引都是同一思想：先定位一半，再深入那一半。
✎练一练
在 100 万个有序元素里做二分查找，大约最多比较几次？
100 万 ≈ 2^20，每次砍一半，最多 约 20 步（log₂10⁶ ≈ 20）。
二分为啥要求数组
有序？如果数组是乱序的，二分还会有效吗？
答案：二分靠“中点值与目标比大小，从而确定去哪半边”，只有数组有序才能保证“目标若存在必在某一半边”。乱序时中点的信息无意义，二分无效（最好先排序，排序后再查）。