二分搜索算法实现 [英] 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，高 = arr.length

Option1: low = 0, high = arr.length

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

Option2: low = 0, high = arr.length - 1

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

Option1: low = 1, high = arr.length

2.循环条件

选项 1: while(low < high)

Option1: while(low < high)

选项 2:while(low <= high)

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.这对应于(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) 除了其他答案之外，这取决于您使用的比较类型(3 态与 2 态输出).对于 2 状态比较和上述答案，您会得到 low=mid+1 或 high=mid.这是理想的，因为很明显每次迭代范围都会变小 -- mid+1 >低 显然，而 mid <;高，因为low(这是循环条件)和(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屋！