二分查找 mid 什么时候要加 1

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 38 天前的主题，其中的信息可能已经有所发展或是发生改变。

有时候用二分查找的时候，

let mid = Math.floor(l + (r - l) / 2)

有时候如果不+1 就死循环了

let mid = Math.floor(l + (r - l) / 2 + 1)

求教，什么时候需要+1 ，什么时候不需要加 1

1 条回复

litmxs

38 天前 via iPhone

你要看你可行区间定义是什么样的，左闭右闭[l,r]还是左闭右开[l,r)，然后要保证每次迭代区间长度都会缩小就可以了，主要就是针对区间长度为 1 和 2 的极端情况。