二分查找 mid 取整方向的问题

Question

二分查找或者其变种问题中, mid 的计算有两种情况:

• 一种是向下取整 mid = (left + right) / 2
• 一种是向上取整 mid = (left + right + 1) / 2

如果取整的方向错误, 很容易造成死循环.
那么应该在什么时候使用向上取整, 什么时候使用向下取整呢?
有什么方法可以判断当前的二分查找 (或者变种问题) 算法的取整的方向是否正确?

Answer 1

liuyubobobo 2020-06-10 04:57:21

造成死循环，是因为这一轮和下一轮的 left 和 right 没有变化，这种情况只会出现在 left 和 right 相差为 1 的时候。

假如 left = 2, right = 3。

mid = (left + right) / 2， mid 为 2

如果下面的判断，left 可能是 mid，下一轮区间就会不变，造成死循环；

mid = (left + right + 1) / 2，mid 为 3

如果下面的判断，right 可能是 mid，下一轮区间就会不变，造成死循环；

继续加油！：）