二分法
学习资料:https://www.hello-algo.com/
基础:二分查找元素
1 | def binary_search(nums:[list[int]], target:int)->int: |
注意,while
后的条件必须包含=
,否则考虑两种情况:
1. 若最后一步执行操作为i = m+1
,且m+1=j
,会导致m+1
不会被搜索到。
2. 若最后一步执行操作为j = m-1
,且m-1=i
,会导致m-1
不会被搜索到。
时间复杂度:
空间复杂度:
以上是针对双闭合区间的代码,即以区间 [i, j] 进行查找 target ;左闭右开区间则指以 [i, j) 进行查找。
1 | def binary_search_lcro(nums: list[int], target: int) -> int: |
假设数组存在多个目标值,上述算法将返回其中任意一个索引,这具体取决于算法在搜索过程中选择的中间位置。因此,此时可考虑引入列表进行优化。
1 | def binary_search_list(nums:[list[int]], target:int)->int: |
值得注意的是,由于 和 都是 int 类型,因此 可能会超出 int 类型的取值范围;为避免大数越界通常采用公式 来计算中点。
适用场景:
- 有序数据
- 数组
- 数据量较大
扩展 1:二分查找插入点
当数组中无重复元素时,只需将二分查找元素代码最后一行返回值换成 i 即可。
函数将返回最后一个小于目标值的后一个索引(当数组中最小值仍大于目标值时,索引将返回 0
;当数组中最大值仍小于目标值时,索引将返回 len(list)
)。
1 | def binary_search_insertion_simple(nums: list[int], target: int) -> int: |
重点:处理数组中的重复元素
这里当然也可以用列表处理(提取最大索引),但K神给出了更简便的思路。
当查找到目标索引时,我们仍然向更小的方向搜索,算法核心仍然是,我们希望返回最后一个小于目标值的后一个索引。对移动的 j 来说,就是首个小于 target 的元素。
1 | def binary_search_insertion(nums: list[int], target: int) -> int: |
我们发现,左闭右开更适合这类“边界”问题。
1 | def binary_search_lcro_insertion(nums:[list[int]], target:int)->int: |
扩展 2:二分查找元素边界
查找左边界
等价于上述问题。
查找右边界
法1:寻找 target+1 的左边界索引再 -1
1 | def binary_search_right_edge(nums: list[int], target: int) -> int: |
法2:构造不存在元素查找
注意,此方法仅适用于 int
类型或选用更小精度的 float
。
当数组不包含 target
时,最终 i 和 j 会分别指向首个大于、小于 target
的元素。
1 | def binary_search_new_ele(nums: list[int], target: int) -> tuple[int, int]: |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 J.Ysanne's blog!
评论