Start, end and stopping condition of Binary Search code

Question

I hope everyone is doing well.

I know there are a lot of questions whose title is very much similar to my question but I have a doubt regarding start and end values :-

• If I use stopping condition as start<=end then, whether start=0 ,end=n/n-1|start=-1,end=n-1/n|start=-2 to end=n-2| start=-3 to end=n-3 **the output is same in all these cases for the below code

  while(l<=r) { int mid=(l+r)/2;

       if(arr[mid]==k)
           return mid;
       else if(k>arr[mid])
           l=mid+1;
       else
           r=mid-1;
   }
  

• From start=-4 to end=-4 the result is wrong.

• I've read the other questions and learned the fact that changing the stopping condition changes the range of start and end (inclusive/ exclusive ) but,

• Why is binary search working for start=0/-1/-2/-3 to end=n/n+1/n+2/n+3? I mean apart from starting mid=(n-2+2)/2<=> n/2, there may be a condition when the target element appears at arr[0].

Thanks for spending your precious time in solving my query.

I hope I've written clearly.

Answer 1

If I use stopping condition as start<=end then, whether start=0 ,end=n/n-1|start=-1,end=n-1/n|start=-2 to end=n-2| start=-3 to end=n-3 the output is same in all these cases for the below code.

This is not true. start and end must start at precisely the first and last index of the array, or there will be cases where the algorithm you provided fails. So assuming zero-based array indexing, start = 0, end = n - 1 is the only correct initialisation for this algorithm.

Here are counter examples for some alternatives:

• start = 0, end = n: if k is a value that is greater than the greatest value in arr, then eventually mid will become equal to n and arr[mid] will be an invalid reference. Depending on the language this may trigger an exception.

• start = -1, end = n - 1: if k is a value that is less than the least value in arr, then eventually mid will become equal to -1 and arr[mid] will be an invalid reference.

• start = -2, end = n - 2. if k == arr[0] and n == 3, the element will not be found, as mid will get the value -1.

• start = -2, end = n + 2. if k == arr[0] and n == 3, the element will not be found, as mid will get the value 1 and in the next iteration it will be -1, so skipping for ever the index 0.

• ...etc