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?

Grazynagreabe

depends on how you update your low and high – Fablan

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.

Tjader

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.

Delitescent

Thank you. Do you think this might be a good practical example? Assuming that each time I update high as mid - 1 and low as mid + 1, then inclusive low and exclusive high assume that the element is inside the array therefore it is safe to terminate without checking the last element. However, inclusive bounds safely check the last element and are used for the case where we are not sure if the element exist? – Grazynagreabe

I suppose that's valid, but the more common case is just in the calling convention. Are you initializing high to be the index of the last element of the array (inclusive bounds), or the length of the array (exclusive bounds)? – Delitescent

lo = 0 and hi = nums.length - 1 – Grazynagreabe

@Grazynagreabe In that case, your bounds are inclusive, so you should use the test low <= high so that you don't stop the loop once you've narrowed down the valid range to a single element. – Delitescent

thank you. One thing, whenever I use low <= high I find it confusing to decide whether to return nums[high] or nums[low] as the end result. I always spend sometimes tracing the index. Is there an easier way to envision the return index? Thanks! – Grazynagreabe