二进制搜索算法的实现 [英] Binary Search algorithm implementations
问题描述
我遇到了多个问题，这些问题使用二进制搜索的变体来得出最终答案.这些问题包括找到数字的平方根的底数，检查数字是否为完美的平方，在旋转数组中找到最小值，在数组中找到数字的第一个索引等.
I have come across multiple problems which use variations of binary search to reach the final answer. These problems include finding floor of square root of number, checking if number is a perfect square or not, finding minimum in rotated array, finding first index of number in array etc.
所有算法都包含一个低，高和中变量，并对其进行了适当修改.
All algorithms contain a low, high and mid variable which are appropriately modified.
我在线阅读了这些算法的几种变体，这些算法中总是很容易出现一个错误，从而使它错过了极端情况.对于以下变体，是否有任何标准可以帮助我理解何时应使用哪个标准?
I read several variations of these algorithms online and there are always high chances of by one error in these algorithms, causing it to miss the corner cases. For the following variations, is there any standard which can help me understand which one should be used when?
1.变量的初始化
选项1:低= 0，高=长度
Option1: low = 0, high = arr.length
选项2:低= 0，高=长度-1
Option2: low = 0, high = arr.length - 1
选项1:低= 1，高=长度长度
Option1: low = 1, high = arr.length
2.循环条件
选项1:while(低<高)
Option1: while(low < high)
选项2:while(低< =高)
Option2: while(low <= high)
3.中间变量计算
选项1:中=(低+高)/2；
Option1: mid = (low + high) / 2;
选项2:中=低+(高-低)/2;
Option2: mid = low + (high - low) / 2;
4.条件检查并更新为高和低
选项1:低=中，高=中
Option1: low = mid AND high = mid
选项2:低=中，高=中-1
Option2: low = mid AND high = mid - 1
选项3:低=中+ 1和高=中
Option3: low = mid + 1 AND high = mid
选项4:低=中+ 1和高=中-1
Option4: low = mid + 1 AND high = mid - 1
假设是3状态输出.数组索引从0开始.
Assumptions taken are 3 state output. Array indices start at 0.
推荐答案
好吧，您可以通过多种方式使它起作用，但是:
Well, you can make it work in lots of ways, but:
1)我使用low=0, high=arr.length.如果我要调用变量low和high，那么即使在搜索结束时，我也总是要low<=high.当arr.length==0
1) I use low=0, high=arr.length. If I'm going to call variables low and high, then I want low<=high always, even at the end of the search. This is also easier to think about when arr.length==0
2)while (low<high).这对应于(1)的答案.循环完成后，我喜欢low==high，因此不必担心要使用哪个.
2) while (low<high). This corresponds to the answer for (1). When the loop is done, I like low==high, so I don't have to worry about which one to use.
3)始终使用mid=low+(high-low)/2或mid = low+((high-low)>>1).当数组过长并给出负面结果时，另一个选项将溢出.
3) Always use mid=low+(high-low)/2 or mid = low+((high-low)>>1). The other option overflows when the array gets too long and gives negative results.
4)除其他答案外，这还取决于您使用的是哪种比较(三态与二态输出).对于二态比较和上述答案，您将得到low=mid+1或high=mid.这是理想的，因为很明显每次迭代的范围都会变小-显然mid+1 > low和mid < high，因为low<high(这是循环条件)和(high-low)/2向下舍入.
4) This depends on what kind of comparison you're using (3-state vs. 2-state output), in addition to the other answers. For 2-state compares and the above-answers, you get low=mid+1 or high=mid. This is ideal, since it's obvious that the range gets smaller every iteration -- mid+1 > low obviously, and mid < high, because low<high (that's the loop condition) and (high-low)/2 rounds downward.
这篇关于二进制搜索算法的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
