0x00 序

二分查找（Binary Search）是一种常见的查找算法，虽然在实际工作中，多是使用语言的标准库中已有的查找函数，手写它的时间并不多。 实际上，二分查找要求列表内的元素有序，对于无序的非字典列表，要使用二分查找，还要先对其排序。

二分查找说起来简单，写起来难。太多人写的时候总是迷糊：

• 循环条件是 while (low < high) 还是 while (low <= high)？
• 缩小搜索范围的时候，是 low = mid 还是 low = mid + 1？
• 甚至在你计算 mid = (low + high) / 2 时还会发生数值溢出的事情…

本文总结了我个人对二分查找的注意点

0x01 基础写法

在列表 nums 中寻找一个数 target，如果存在，返回其索引，否则返回 -1。这个题可以在 leetcode-cn 找到：704.二分查找

以下是两种常见的写法：

所有代码均为 python 版本

 1# 写法一
 2def binarySearchV1(nums: List[int], target: int) -> int:
 3    low, high = 0, len(nums) 
 4    while low < high: 
 5        mid = low + (high - low) // 2 # 防止越界
 6        if nums[mid] < target:
 7            low = mid + 1  
 8        elif nums[mid] > target:
 9            high = mid
10        else:
11            return mid
12    return -1

 1# 写法二
 2def binarySearchV2(nums: List[int], target: int) -> int:
 3    low, high = 0, len(nums) - 1
 4    while low <= high: 
 5        mid = low + (high - low) // 2 # 防止越界
 6        if nums[mid] < target:
 7            low = mid + 1  
 8        elif nums[mid] > target:
 9            high = mid - 1 
10        else:
11            return mid
12    return -1

1. 搜索范围如何确定

当 high 取数组长度 len(nums) 时，搜索范围即为 [low, high)（左闭右开区间）； 而当 high 取数组长度减 1 len(nums) - 1 时，搜索范围为 [low, high]（闭区间）。

这两种都可以，但关键的是，后面的 while 循环条件和修改 mid 值，必须要保证搜索范围不遗漏、不重复。 也就是每次循环完得到新的范围，要把不符合条件的另一半数据准确地舍去。

2. 循环条件如何确定

到底是 low < high 还是 low <= high？

这其实要根据 1 中的选择来判断：

如果搜索范围为 [low, high)，那么当要跳出循环，只要 low == high 就可以了，比如 [3, 3)，因为这时候区间里是没有值的，当然要跳出循环，此时只有 low < high 满足。 因为如果是 low <= high 的话，当 low == high 时，while 循环仍会继续，这样显然就不对了。

那么到这里可以总结右侧 high 取值和 while 循环条件的关系：

3. 新的搜索范围如何确定

在前面说到，要保证搜索范围不遗漏、不重复，就是在每次缩小范围时给 mid 赋值。 由于每次判断的值是 nums[mid]，mid 是判断过的，下一个范围如何确定，实际上还是要根据 1 中的选择来判断：

如果搜索范围为 [low, high)，且要保证 mid 已经判断过的事实，当舍弃右边时，那么 high = mid，当舍弃左边时，那么 low = mid + 1； 如果搜索范围为 [low, high]，且要保证 mid 已经判断过的事实，当舍弃右边时，那么 high = mid - 1，当舍弃左边时，那么 low = mid + 1。

可以看到，low 的改变始终是 mid + 1，为什么？因为从始至终，low 在最开始的取值就是 0。当然也可以取 -1，非要搞成左开区间也没人拦着…

再到这里，可以将之前的总结关系扩充如下：

0x02 总结

至此，可以发现，当第一步就选择了计算 high = len(nums) - 1 时，后面每一步都要相应的多写一点…

所以上面分析了这么一通，如果还记不住的话，只要记得，要是一开始就简单，后面也会简单；要是一开始就搞复杂，后面也要搞复杂… 😂

有空的话我会整理一下二分查找的几种变体，待续…