arrays - 二进制搜索算法实现

Question

我遇到过多个使用二进制搜索 变体来得出最终答案的问题。这些问题包括找到数字的平方根的下限、检查数字是否是完全平方数、在旋转数组中找到最小值、在数组中找到数字的第一个索引等。

所有算法都包含经过适当修改的低、高和中变量。

我在网上阅读了这些算法的几种变体，这些算法总是很可能出现一个错误，导致它错过极端情况。对于以下变体，是否有任何标准可以帮助我理解何时应该使用哪个？

<强>1。变量的初始化

选项 1:低 = 0，高 = arr.length

选项 2:低 = 0，高 = arr.length - 1

选项 1:低 = 1，高 = arr.length

<强>2。循环条件

选项 1:同时(低 < 高)

选项 2:同时(低 <= 高)

<强>3。中变量计算

选项 1:中 = (低 + 高)/2;

选项2:中=低+(高-低)/2；

<强>4。条件检查和更新到低和高

选项 1:低 = 中 AND 高 = 中

选项 2:低 = 中 AND 高 = 中 - 1

选项 3:低 = 中 + 1 和高 = 中

选项 4:低 = 中 + 1 和高 = 中 - 1

编辑:采用的假设是 3 态输出。数组索引从 0 开始。

Answer 1

好吧，您可以通过多种方式使其发挥作用，但是:

1) 我使用 low=0, high=arr.length .如果我要调用变量 low和 high , 那么我要 low<=high总是，甚至在搜索结束时。这也更容易想到什么时候arr.length==0

2) while (low<high) .这对应于 (1) 的答案。循环完成后，我喜欢 low==high , 所以我不必担心使用哪一个。

3) 始终使用 mid=low+(high-low)/2或 mid = low+((high-low)>>1) .当数组变得太长并给出负面结果时，另一个选项会溢出。

4) 除了其他答案外，这还取决于您使用的比较类型(三态与二态输出)。对于 2 态比较和上述答案，你得到 low=mid+1或 high=mid .这是理想的，因为很明显每次迭代范围都会变小 -- mid+1 > low显然，和mid < high ，因为 low<high (这是循环条件)和 (high-low)/2向下舍入。