二分查找：每一次排除一半
有序数组里找 target——比较中点，扔掉不含答案的那一半。
维护查找区间 [left, right]。每次取中点 mid = left + (right−left)/2：nums[mid] 等于 target 就命中；小于 target 说明答案在右半边，令 left = mid+1；大于 target 说明在左半边，令 right = mid−1。区间为空（left > right）仍未命中则返回 −1。O(log n)。
给定一个升序数组 nums 和一个目标值 target，返回它在数组中的下标；不存在返回 −1。
示例：nums = [−1,0,3,5,9,12]，target = 9 → 4。
二分的关键不是「找中点」这个动作，而是理解它背后的不变量。
为什么能折半
数组升序：如果 nums[mid] < target，那么 mid 及左侧所有元素都小于 target，全部可以排除。
这就是二分的全部：根据中点与 target 的大小关系，确定性地排除一半。
所以每一步区间长度减半，log₂n 步后区间为空或命中。
前提折半依赖单调性：只有升序（或降序），才能从中点推出「哪半边还有答案」。
折半演示
nums = [−1,0,3,5,9,12]，target = 9。
left=0, right=5, mid=2。nums[2]=3 < 9，排除左半边，left=3。
left=3, right=5, mid=4。nums[4]=9 == 9，命中，返回 4。
只用两步就找到——每次排除一半的力量。
不变量：target 永远只在区间里
关键不变量：如果 target 存在，它一定在 [left, right] 里。
每次更新都严格排除「确定不含 target」的那半边，所以不变量保持。
循环条件 while (left <= right)：left == right 时还有一个元素要检查，不能停。
left = mid+1、right = mid−1（而不是 mid）是为了排除 mid 本身——mid 已被比较过，不再属于搜索区间。
未命中：区间收缩到空
target = 2 在上述数组里不存在。
mid=2 时 nums[2]=3 > 2 → right=1。区间 [0,1]。
mid=0 时 nums[0]=−1 < 2 → left=1。区间 [1,1]。
mid=1 时 nums[1]=0 < 2 → left=2。此时 left > right，区间为空，返回 −1。
注意循环结束位置：left 恰好是「第一个大于 target」的下标，这给 LC35（搜索插入位置）留了伏笔。
七行 Go：闭区间二分
func search(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] == target { return mid }if nums[mid] < target { left = mid + 1 } else { right = mid - 1 }}return -1}
1闭区间 [left, right]。
2区间非空就继续。
3防止溢出的中点写法。
4命中返回。
5排除不含答案的半边。
总结
比较中点、排除半边、维护不变量——O(log n) 有序查找的标准动作。
- 单调性是二分的前提。
- 不变量「target 只在 [left,right] 里」约束了每一步更新。
- left=mid+1、right=mid−1 排除已比较的 mid。