二分查找总结
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
循环条件的关系:
右侧最初取值 | 循环条件 |
---|---|
len(nums) | low < high |
len(nums) - 1 | low <= high |
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
,非要搞成左开区间也没人拦着…
再到这里,可以将之前的总结关系扩充如下:
右侧最初取值 | 循环条件 | 右侧缩小范围时取值 |
---|---|---|
len(nums) | low < high | mid |
len(nums) - 1 | low <= high | mid - 1 |
0x02 总结
至此,可以发现,当第一步就选择了计算 high = len(nums) - 1
时,后面每一步都要相应的多写一点…
所以上面分析了这么一通,如果还记不住的话,只要记得,要是一开始就简单,后面也会简单;要是一开始就搞复杂,后面也要搞复杂… 😂
有空的话我会整理一下二分查找的几种变体,待续…