二分查找

一句话：二分查找的必要条件不是”数组有序”，而是**“答案空间上存在一个单调的判定条件”**——能把问题转化成”在一段区间里找到条件由假变真的那个分界点”，就能二分，哪怕数组本身看起来是”无序”的。

二分的本质是找分界点，不是找有序数组里的值

33-搜索旋转排序数组、153-寻找旋转排序数组中的最小值 表面上数组不是整体有序的（被旋转过），但从任意一点切开，两半里必有一半是有序的——每次二分时先判断哪一半有序，再判断目标值是否落在那一半的范围内，来决定往哪边收缩。这类题的坑不是二分本身，是”判断目标在有序的哪一半”这一步的边界条件（等号、旋转点恰好在中点等）容易写错，需要每种情况都在草稿上枚举一遍再写代码。

69-x的平方根 和 4-寻找两个正序数组的中位数 更进一步说明”二分不需要显式数组”：69 二分的是”答案”本身（在 [0, x] 范围内找满足 mid*mid <= x 的最大值）；4 二分的是”在两个数组里各切多少个元素”，判定条件是”左半部分的最大值 ≤ 右半部分的最小值”——只要判定条件具有单调性（一旦满足就一直满足，或一旦不满足就一直不满足），就可以对”答案”或”切分点”本身二分，不需要问题看起来像”在数组里找值”。

与树结构的联系：跳表

1206-跳表 是把”二分”的思想从数组搬到链表上的产物：普通链表只能一个个遍历，跳表通过额外维护多层”快速通道”，让查找也能做到期望 O(log n)——用空间换来了链表上原本做不到的二分。它和平衡树、哈希表是同一个问题（有序结构上的高效查找）的三种不同解法，对比见树。

边界写法：左闭右闭还是左闭右开

二分查找最容易犯的错不是算法思路，是循环不变量与边界写法不一致：选定”左闭右闭 [left, right]”还是”左闭右开 [left, right)”之后，while 的条件（<= 还是 <）、right 的初始值、收缩时是 mid 还是 mid±1，四处必须自洽，任何一处沿用另一种写法的习惯就会死循环或漏解。建议固定一种写法反复用，不要每次现场发明。