Binary Search Terminating Condition

Question

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?

Answer 1

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.

Answer 2

The two termination conditions you're listing are often used depending on whether low and high are inclusive or exclusive. If your bounds are inclusive, then when low = high there's one element left in the array to check and the inner loop should run another time. Therefore, a test of whether low ≤ high is appropriate. On the other hand, if low is inclusive and high is exclusive, then when low = high you've exhausted all the elements and are done, so a test of the form low < high is more appropriate.