Confuse in Binary Search when to use left < right ; left <= right ; and few more

Question

I've difficulty in understanding when to use:

while (left < right ) {
}

vs when to use:

while (left <= right ) {
}

Also while setting left and right boundaries sometimes we use:

left = mid 

and sometime we use

left = mid + 1;

similarly

right = mid; vs
right = mid - 1;

Is there any fundamental I am missing in knowledge of Binary search ?

Counterpoint

Hope this article help you - medium.com/swlh/… – Diastole

Answer 1

The basic idea is to search and find the element:

public static int indexOf(int[] array, int target) {
   int lo = 0, hi = a.length - 1;
   while (lo <= hi) {
      // Key is in a[lo..hi] or may be it is not present.
      int mid = lo + (hi - lo) / 2;
      if      (target < a[mid]) hi = mid - 1;
      else if (target > a[mid]) lo = mid + 1;
      else return mid;
   }
   return -1;
}

We can also use mid = (lo + hi) >>> 1 to compute the mid but using (lo+hi)/2 may cause overflow. Now the confusion part:

We use while (lo <= hi) if we are returning the match from inside the loop. We use while (lo < hi) when we want to exit the loop first and then use the result of lo or hi to return the match.

Good intro for binary search use cases: https://leetcode.com/discuss/general-discussion/786126/Python-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

Halfprice

So do we know which one of the indexes (lo or high) to return or does that depend on the questions? If so, is it always simpler to just return within the loop? – Faradmeter

@Faradmeter depends on the scenario of returning min or max value in a problem. – Halfprice

Answer 2

When you divide an array you find the mid index. At this time you have two parts with a mid index. Since the array is sorted you compare the search element with mid index value.

If the search value is smaller than mid index value you know it is at left side otherwise it is at right side.

Now, you repeat the above step (divide into two parts, mid index etc.) for either left half (index 0 to mid - 1) or right half (index mid +1 to end). If the search value is same as mid index value then element is found and you stop processing.

This divide and compare process continues until you find the search element or left and right index (initially 0 and length-1) overlaps. Thats why the condition left <= right.

Mont

Yes I agree that part, but sometime left < right works and sometime not. that is my confusion. – Counterpoint

Yes left < right would work. You are checking my left index of the array part is not same as right index or exceeding the right index. If so no need to process further. So, I will process until left < right – Mont

For binary search visualisation check this: cs.usfca.edu/~galles/visualization/Search.html. If you find this answer clarifies your doubts please accept it. – Mont

Answer 3

use left <= right when you are changing the mid index in the loop

 mid = right -1
 mid = left +1

use left < right when you are assigning the left and right directly to mid

right = mid
left = mid+1

Pygmy