Can binary search fail if low = mid instead of mid + 1?

I am trying to understand how binary search works. The basic code, for anyone who doesn't know, is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  while (l <= r) { 
        int m = l + (r - l) / 2; 
  
        // Check if x is present at mid 
        if (arr[m] == x) 
            return m; 
  
        // If x greater, ignore left half 
        if (arr[m] < x) 
            l = m + 1; 
  
        // If x is smaller, ignore right half 
        else
            r = m - 1; 
    } 


My question is, will a binary search fail or access garbage memory if low equaled mid instead of mid + 1? Or is it just really inefficient?
If you made it L=M instead of L=M+1 it can fail.

Consider a two-element array { 4, 6 } and look for the value 5.

Initially L=0, R=1. M is calculated by truncation as 0.
If you set L=M in response to 4<5 then L would stay 0 for ever more.
has nothing with either one instead it depends on what are contents of arr and x
Last edited on
Registered users can post here. Sign in or register to post.