二进制搜索终止条件 [英] Binary Search Terminating Condition

问题描述

每当我迭代执行二进制搜索时，我总是对应该使用 while(low< high)还是 while(low< = high)感到困惑./p>

虽然两者都可以，但是有人可以告诉我一个人相对于另一个人的实际优势是什么吗?

解决方案

除了@templatetypedef所说的外，还必须提及的是，当边界为 inclusive 时，终止条件应仅为 low< = high ，如果终止条件保持为低<高将导致搜索中跳过1个元素.同样，当边界为排他性时，终止条件应仅为 low<高，如果条件低< =高，则会导致索引超出范围.

我将在此处尝试通过示例进行解释:

假设数组为[4，5，6] ans，我们要搜索元素6.这里数组的长度为3.

初始化:我们将low设置为0.我们可以将high设置为2或将high设置为3.(即，长度-1或长度)

具有 high 的运行循环，其初始化为Length-1

低= 0，高= 2

 第一次迭代低= 0，高= 2，中= 1.array [middle]为5，所以low =中间+ 1即2 

使用if(low< high)循环进行第二次迭代时将终止而无需在位置2处搜索元素，因此应该是if(low< = high)

 在第二次迭代中使用if(low< = high)低= 2，高= 2，中= 2，array [middle] == x，所以我们返回2. 

以 high 初始化为Length

的运行循环

低= 0，高= 3

 第一次迭代低= 0，高= 3，中= 1.array [middle]为5，所以low =中间+ 1即2在第二次迭代中使用if(low< high)低= 2，高= 3，中=2.array [middle] == x，我们返回2. 

请注意:条件不能低到< =高，因为如果数组中不存在x，它将导致循环在第二次迭代中运行低= 3和高= 3，这将导致索引循环第3次运行时超出范围.

Whenever I perform binary search iteratively I am always confused about whether I should use while (low < high) or while(low <= high).

Although both will work, can someone tell me what might be the practical advantage of one over the other?

解决方案

In addition to what @templatetypedef said, it is also important to mention that when bounds are inclusive terminating condition should only be low <= high, if terminating condition is kept low < high it will cause 1 element skipped in search. Also when bounds are exclusive terminating condition should only be low < high, if condition is low <= high, it will cause index out of bounds.

I will try to explain it with an example here:

Suppose array is [4, 5, 6] ans we want to search for element 6. Length of array here is 3.

Initialization: We set low = 0. We can either set high = 2 or high = 3. (i.e. Length -1 or Length)

Running loop with high initialized with Length - 1

low = 0, high = 2

In first iteration
    low = 0, high = 2 and middle = 1.
    array[middle] is 5, so low = middle + 1 i.e. 2

On second iteration with if(low < high) loop would terminate without searching for element at location 2, so it should be if(low <= high)

 In second iteration with if (low <= high) 
    low = 2, high = 2, middle = 2, array[middle] == x, so we return 2.

Running loop with high initialized with Length

low = 0, high = 3

In first iteration
    low = 0, high = 3 and middle = 1.
    array[middle] is 5, so low = middle + 1 i.e. 2

In second iteration with if(low < high)
    low = 2, high = 3, middle = 2. array[middle] == x, we return 2.

Note that condition can not be low <= high because if x is not present in array it will cause loop to run low = 3 and high = 3 in second iteration and that will cause index out of bounds when loop runs for 3rd time.

这篇关于二进制搜索终止条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！