Binary search · part 1 · the core

Two boundaries,
four queries, three skeletons.

A sorted array splits into three regions at any target t. Two boundaries separate them; each of the four queries returns the index on one side of one boundary. Step through all of it on a real 100-element array — every lo, every hi, every mid. The third skeleton — the open interval (lo, hi) — answers all four with one loop, and makes the other two unnecessary.

Target & array

n = 100
Canonical cases
Click any cell in the array below to set t to its value.
step 0 / 0
← → step   space play   r reset
a[i] < t a[i] == t  (the equal range) a[i] > t boundary 1 boundary 2

This iteration

lower_bound

The code, executing

C++

    

  


  
  

    

      
Trace

      
    

    

  


  
  

    

      
All four queries at this t

      
    

    

    

  


  
  

    

      
Break a rule, watch the damage

      the three rules, falsified
    

    

      
Each rule below is asserted in the notes. Turn one off and the visualizer above runs the broken algorithm instead — same array, same target, same panels. Then switch to the invariant (lo, hi) tab with a rule still broken: all three have nothing left to break there, which is the case for preferring that skeleton.

      

        
        
        
        
      

    

    

      

        
Rule 1 · rounding

        
The side that keeps mid is the side mid must round toward.

        
lo = mid pairs with ceil, mid = lo + (hi - lo + 1) / 2. hi = mid pairs with floor, mid = lo + (hi - lo) / 2. Get it backwards and a two-element window can never shrink.

      

      

        
Rule 2 · the exit check

        
The exit check must re-test the predicate the loop searched on.

        
The loop converges to a candidate. If the predicate was never true anywhere, lo just sits at the edge of the range, unverified — and you return an index that answers nothing.

      

      

        
Rule 3 · the sentinel

        
“First” queries tolerate hi = n. “Last” queries do not.

        
In a half-open loop mid < hi always, so n is never dereferenced. A closed loop takes mid up to hi itself — and there is no legal sentinel below 0 on the other end.

      

    

  


  
  

    
Self-test
brute force is the oracle