Binary Search: O(log n) or O(∞)?

Jon Bentley asked professional programmers to implement binary search. Over 90% wrote subtly broken code. Not because the algorithm is hard. Because they never answered one question before touching the keyboard: is rhs pointing at a valid element, or one past it?

That single omission is the root of every off-by-one error, wrong return value, and infinite loop I have ever seen in binary search.

The Interval Is the Contract

Two styles exist. Pick one. Never switch mid-implementation.

[lhs, rhs] — closed. Both ends are candidates.

 [ 10   20   30   40   50   60   70 ]
   ^              ^              ^
  lhs            mid            rhs
                                 └── valid element. will be visited.

 lhs = mid + 1      rhs = mid - 1      while (lhs <= rhs)

[lhs, rhs) — half-open. rhs is a fence post.

 [ 10   20   30   40   50   60   70 ]   ·
   ^              ^                     ^
  lhs            mid                   rhs
                                        └── never visited. one past the end.

 lhs = mid + 1      rhs = mid           while (lhs < rhs)

Mix them and you get silent wrong answers. The compiler will not save you.

The Infinite Loop

Finding the last valid element requires retaining mid as a candidate: lhs = mid.

Here is what happens when the space shrinks to two elements:

 Space of size 2:
 [ 40   50 ]
   ^    ^
  lhs  rhs

 mid = lhs + (rhs - lhs) / 2
     = 0   + (  1 -   0) / 2
     = 0   ──► resolves to lhs

 Predicate says valid → lhs = mid = 0
                                    └── no-op. pointers do not move. forever.

The predicate is correct. Floor division betrayed you.

The rule: lhs = mid always requires a ceiling midpoint. This applies to the half-open [lhs, rhs) form — the only form where lhs = mid is a valid update.

 rhs = mid  →  mid = lhs + (rhs - lhs) / 2     ← floor   (safe)
 lhs = mid  →  mid = rhs - (rhs - lhs) / 2     ← ceiling (safe)

With ceiling, the size-2 case: mid = 1 - (1-0)/2 = 1 = rhs. Predicate valid → lhs = 1. Check 1 < 1 → false. Loop exits.

The Overflow Nobody Noticed for 20 Years

Every textbook wrote mid = (lhs + rhs) / 2. In 2006, Joshua Bloch found it had been broken in Java’s standard library since 1997. On arrays near 1 billion elements, lhs + rhs silently overflows a 32-bit integer. mid goes negative. The program crashes.

 Broken:  (lhs + rhs) / 2          ← overflows at ~2³¹ elements
 Safe:    lhs + (rhs - lhs) / 2    ← distance from lhs, always fits

Never use (lhs + rhs) >> 1 in production without an explicit unsigned cast — same overflow, different syntax.

The Decision Table

Goal	Interval	Loop	lhs update	rhs update	mid
Exact match	`[lhs, rhs]`	`<= rhs`	`mid + 1`	`mid - 1`	floor
First occurrence	`[lhs, rhs)`	`< rhs`	`mid + 1`	`mid`	floor
Last occurrence	`[lhs, rhs)`	`< rhs`	`mid`	`mid`	ceiling

Once you commit to the interval, every column follows. mid is the only choice that can still surprise you.

Jon Bentley, Programming Pearls (1986). Joshua Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken”, Google Research Blog (2006). CP-Algorithms: Binary Search.