二分查找
本文的内容总结于该视频
用二分查找来解决这四个问题时,边界条件很容易出错
让我们从另一个角度来看这个问题:
有红蓝两个指针,如何让这两个指针移动到各自的边界
伪代码:
对于上面的四种情况,我们只要控制IsBlue
和要返回红色指针还是蓝色指针就可以做到
以下是我用python实现的代码:
lower_bound:
def lower_bound(arr: list, n) -> int:
l, r = -1, len(arr)
while l + 1 != r:
m = (l + r) // 2
if arr[m] < n:
l = m
else:
r = m
return r
upper_bound:
def upper_bound(arr: list, n) -> int:
l, r = -1, len(arr)
while l + 1 != r:
m = (l + r) // 2
if arr[m] <= n:
l = m
else:
r = m
return
思考
通过二分查找的方式计算\(\sqrt2\),要求误差小于\(10^{-6}\)
# 显然 2 ** 0.5 小于2,大于0
l, r = 0, 2
while l + 10e-6 < r:
m = (l + r) / 2
if m ** 2 < 2:
l = m
else:
r = m
print(r)
# 输出1.414215087890625