二分查找

有序数组里找一个 target，返回什么

给一个升序（从小到大排好）、无重复数字的数组 nums 和目标值 target：在数组里就返回下标，不在返回 -1。题面例子 nums=[-1,0,3,5,9,12]，找 9 返回下标 4，找 2 返回 -1。题目还卡死 O(log n)，不许一个个挨着找。

一个个往后比，为什么撑不到 O(log n)

笨办法是从头扫到尾，一个个和 target 比。数组有 n 个数，最坏（target 排末尾或不存在）要比满 n 次，这就是 O(n)（大 O 记号，衡量数据规模增大时操作量的放大倍数）。n 到百万就得比百万次，O(log n) 把这条路堵死了。

凭什么敢一次丢掉一半数不看

钥匙全在『有序』二字上。看正中间的 nums[mid]（mid 是中点下标）和 target 比：nums[mid] 小于 target，左边只会更小、够不着，左半连 mid 一起扔掉；大于 target 则右半作废。一比砍掉一半，剩下的才是 target 藏身处，这就是二分查找——每次砍掉一半候选的找法。乱序里左右没规律，砍哪半都可能误伤 target。

看中点该往哪半收，闭区间怎么不越界

用两个指针 l、r 圈住没排除的范围，起初 l=0、r=n-1，两端都算数，这叫闭区间 [l,r]。每轮取中点 mid=l+(r-l)//2 和 target 比：相等直接返回 mid；小于 target，l 跳到 mid+1；大于 target，r 退到 mid-1。

这里藏着一条循环不变量（每一轮都成立的保证）：target 若存在，就一定还在 [l,r] 内。收缩必须跨过 mid——比过的 mid 已排除，l 或 r 落到 mid 下一格，范围才真变小。循环条件写 while l<=r，因为 l==r 时闭区间里还剩一格没查。

[-1,0,3,5,9,12] 里找 9、找 2 各几轮

先找 9。l=0、r=5，mid=0+(5-0)//2=2，nums[2]=3 比 9 小，l 跳到 3。第二轮 l=3、r=5，mid=3+(5-3)//2=4，nums[4]=9 相等，返回下标 4，两轮命中。

再找 2。l=0、r=5，mid=2，nums[2]=3 比 2 大，r 退到 1。第二轮 l=0、r=1，mid=0，nums[0]=-1 比 2 小，l 跳到 1。第三轮 l=1、r=1，mid=1，nums[1]=0 比 2 小，l 跳到 2，此时 l 超过 r，范围空了，返回 -1。

缩不动的死循环，卡在 mid 没跨过去

收缩那步最阴：把 l=mid+1 写成 l=mid，比过的 mid 没跨过去，l 卡着不动就成了缩不动的死循环。循环条件也别写成 while l<r，闭区间里 l==r 那一格会被漏掉。mid 写成 (l+r)//2 看着没差，可数组一大 l+r 会超整数上限溢出，得写 l+(r-l)//2 绕开。

复杂度上，每比一次范围减半，n 个数最多 log₂n 次收敛，时间 O(log n)；只用 l、r、mid 三个变量，空间 O(1)。百万个数约 20 次比较，比 O(n) 快几个数量级。