怎么写对二分
date
Mar 29, 2024
tags
slug
how-to-write-binary-search-correctly
status
Published
summary
一文带你彻底写对二分。
type
Post
总结：
通过 bisection 来写二分
Bisection
给出
bisection 定义：给定一个返回布尔值的函数
f ，在序列 a 中找到最小的索引 k ≥ 0 ，使得所有索引 i < k 有 f(a[i]) == false ，所有索引 j ≥ k 有 f(a[j]) == true 。(精确将数组分成了两半）因为
bisection 的写法可以是固定的，手写二分时，先写出 bisection ，然后根据需求定义函数 f 找出自己想要的索引。这样就只需要思考定义布尔函数，不再需要注意各种边界问题。大大减少了精神负担。
然后
bisection 的写法：解释：
- 首先对数组
arr的搜索范围固定是[0:len(arr) - 1]闭区间，也就是i < j条件，始终保持访问的是合法下标，但注意最后返回的是 i ，有可能整个数组都没有满足条件的索引导致i = len(arr)。
mid需要防溢出（Python 这里就没必要了），同时保证mid永远不可能等于j，因为向下取整的除法，会让j和i相差 1 的时候偏向i。
- 我们需要确保循环能够正确终止，在不满足
f条件判断时，可以放心更新i = mid + 1以缩小搜索范围，同时mid的计算方式保证j = mid也是缩小搜索范围，确保每次循环都能将搜索范围减 1，最终i == j时循环终止。
应用
- 查找有序数组中是否存在 target :
- 查找有序数组中第一个大于
target的索引：
参考：
