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 ?

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.

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.