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

This topic created in 587 days ago, the information mentioned may be changed or developed.

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

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

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

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

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

1 replies

litmxs

Oct 21, 2024 via iPhone

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