福
福

雨辰枫司的小栈

二分算法

  • 469 字
  • 条评论
  1. 1. 模板一
  2. 2. 模板二

算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

模板一

将区间划分为 [l , mid] 和 [mid + 1 , r] , 这时候只要更新 l = mid + 1 或者 r = mid ， mid 不需要加一

1
2
3
4
5
6
7
while l < r:
    mid = (l + r) >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
return l

模板二

将区间划分为 [l , mid - 1] 和 [mid , r] , 这时候只要更新 l = mid 或者 r = mid - 1 ， 为了防止死循环，mid 需要加一

1
2
3
4
5
6
7
while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1
return l
, ,