二进制搜索算法实现

Question

我遇到了多个问题，它们使用二进制搜索的变体来获得最终答案。这些问题包括:求数的平方根地板、检验数是否为完全正方形、在旋转数组中求最小值、在数组中求数的第一指标等。

所有算法都包含一个低、高和中变量，并对其进行了适当的修改。

我在网上读到了这些算法的几个变体，这些算法中总是有一个错误的可能性很高，导致它忽略了角落的情况。对于以下的变体，有什么标准可以帮助我理解什么时候应该使用哪一种呢？

1.变量的初始化

Option1: low = 0，high = arr.length

Option2:低= 0，高= arr.length -1

Option1:低= 1，高= arr.length

2.循环的条件

Option1:时间(低<高)

Option2:同时(低<=高)

3.中间变量计算

Option1: mid =(低+高)/ 2；

Option2: mid =低+(高-低)/ 2；

4.状态检查和更新到低和高

Option1:低=中，高=中

Option2:低=中，高=中间-1

Option3:低= mid +1和高= mid

Option4:低= mid +1和高= mid -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)这取决于您使用的是哪种比较(3状态与2状态输出)，以及其他答案。对于2状态比较和上面的答案，您可以得到low=mid+1或high=mid.这是理想的，因为很明显，每次迭代的范围都会变小--显然是mid+1 > low和mid < high，因为low<high (这是循环条件)和(high-low)/2向下舍入。

Answer 2

这并不是说你提到的选择越来越糟糕。通常，它只取决于一个实现，例如，如果您通过high=arr.length，那么您宁愿编写while(low < high)而不是while(low <= high)。

事实上，这些差异中的一些可能有的含义。如果我们考虑二进制搜索算法来找到数组A中的X数，并且会有一些(不仅仅是一个)元素等于X，那么您可以找到第一个或最后一个的索引--这取决于实现。