How do I know whether to use `left <= right` or `left < right`?

Look at your initial `right` pointer. If `right = nums.length - 1`, your search space is closed and includes index `right`, requiring `while (left <= right)`. If `right = nums.length`, your search space is half-open and excludes index `right`, requiring `while (left < right)`.

Why did Java's `Arrays.binarySearch` contain a bug for over nine years?

The implementation used `int mid = (low + high) >>> 1` in later patches, but originally used `int mid = (low + high) / 2`. When `low + high` exceeded `2,147,483,647`, the integer sum overflowed to a negative value, causing the division to return a negative midpoint and throwing an unexpected index error.

What is the difference between exact match and lower bound binary search?

An exact match search stops as soon as `nums[mid] === target` is found. A lower bound search continues even after finding a matching value to identify the first occurrence (leftmost index) where `nums[mid] >= target`. Lower bound is the foundation for finding duplicates and inserting elements in sorted order.

How does binary search work when there is no array (binary search on answer)?

Binary search on answer applies the same interval reduction to a mathematical range `[minPossible, maxPossible]` rather than indices. As long as a condition is monotonic (e.g. "if speed $k$ works, any speed $> k$ also works"), you can evaluate `canComplete(mid)` and shrink the search range logarithmically.

All Articles

9 min read

Why Binary Search Breaks: Visualizing left <= right vs left < right

Q: How do I know whether to use `left <= right` or `left < right`?

Look at your initial `right` pointer. If `right = nums.length - 1`, your search space is closed and includes index `right`, requiring `while (left <= right)`. If `right = nums.length`, your search space is half-open and excludes index `right`, requiring `while (left < right)`.

Q: Why did Java's `Arrays.binarySearch` contain a bug for over nine years?

The implementation used `int mid = (low + high) >>> 1` in later patches, but originally used `int mid = (low + high) / 2`. When `low + high` exceeded `2,147,483,647`, the integer sum overflowed to a negative value, causing the division to return a negative midpoint and throwing an unexpected index error.

Learn why binary search off-by-one errors happen, when to use inclusive vs half-open intervals, how to prevent infinite loops, and how to visualize shrinking boundaries.

Why Binary Search Breaks: Visualizing `left <= right` vs `left < right`

You write while (left < right) instead of while (left <= right). Your code passes the first four sample tests, then hangs indefinitely on a single-element array [5] with target 5. You change the condition to <=, run the tests again, and a two-element array throws an out-of-bounds error or gets trapped in an infinite loop.

Binary search is often the first non-trivial algorithm programmers learn. It looks deceptively simple: seven lines of code, two pointers, and a division by two. Yet it causes more failed interview screens and production off-by-one errors than algorithms twice its length.

Computer science pioneer Donald Knuth observed that while the first binary search was published in 1946, the first completely bug-free version was not published until 1962—sixteen years later. In 2006, Joshua Bloch discovered a critical integer overflow bug in Java’s standard library implementation of Arrays.binarySearch, which had gone unnoticed for over nine years.

If seasoned compiler engineers and language designers struggled with seven lines of binary search, guessing your boundary conditions on a whiteboard will rarely work. To write binary search without bugs, you must stop guessing whether to add or subtract 1. You need to visualize the search space as an active window with a strict mathematical contract.

The Mental Model: What is the Search Space Contract?

Every binary search bug stems from a single root cause: the loop condition does not match the search interval contract.

Before writing a single line of code, you must decide what the indices left and right represent. There are two primary templates in computer science:

The Closed Interval [left, right]: Both endpoints are inclusive. Any index from left up to and including right could contain the target.
The Half-Open Interval [left, right): The left endpoint is inclusive, but the right endpoint is exclusive. Any index from left up to right - 1 could contain the target.

Closed Interval [left, right]:
Index:     0    1    2    3    4    5
Array:   [ 1,   3,   5,   7,   9,  11 ]
           ▲                        ▲
         left                     right
Target can be at index 0, 1, 2, 3, 4, OR 5.

Half-Open Interval [left, right):
Index:     0    1    2    3    4    5  |  6
Array:   [ 1,   3,   5,   7,   9,  11 ] |
           ▲                             ▲
         left                          right (nums.length)
Target can be at index 0, 1, 2, 3, 4, OR 5. Index 6 is excluded.

Once you choose your contract, every other line of code—the initial values, the while condition, and the pointer updates—is dictated by that choice. Mixing the rules of one template with the rules of the other guarantees an off-by-one error.

Template 1: The Closed Interval (`left <= right`)

This is the standard template taught for exact match lookups (e.g. LeetCode 704: Binary Search).

The Invariant Rules

Initial State: left = 0, right = nums.length - 1
Loop Condition: while (left <= right)
Left Update: left = mid + 1
Right Update: right = mid - 1

binarySearchClosed.ts· TypeScript

Trace Code

export function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    // Safe midpoint calculation avoiding integer overflow
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] === target) {
      return mid; // Target found
    } else if (nums[mid] < target) {
      left = mid + 1; // Discard mid and everything to its left
    } else {
      right = mid - 1; // Discard mid and everything to its right
    }
  }

  return -1; // Target not present
}

Why Must It Be `left <= right`?

Ask yourself: When is the search space truly empty in a closed interval [left, right]?

If left = 2 and right = 4, the interval [2, 4] contains 3 candidates (indices 2, 3, 4).
If left = 2 and right = 2, the interval [2, 2] contains 1 candidate (index 2).
If left = 3 and right = 2, the interval [3, 2] contains 0 candidates.

When left === right, there is still one valid element left to inspect. If you write while (left < right), the loop terminates prematurely when only one element remains. If that final element happens to be your target, your function returns -1 erroneously.

Trace 1: Target Present (`nums = [1, 3, 5, 7, 9, 11]`, `target = 7`)

Closed Interval Execution Trace: Target Found· TEMPLATE 1

4 steps

Step	left	right	mid	nums[mid]	Evaluation	Next Action
0	0	5	—	—	Initial range [0..5]	Compute mid = 0 + Math.floor(5/2) = 2
1	0	5	2	5	5 < 7 (Too small)	Target must be right of 2. left = 2 + 1 = 3
2	3	5	4	9	9 > 7 (Too large)	Target must be left of 4. right = 4 - 1 = 3
3	3	3	3	7	7 === 7 (Match!)	Return index `3`

Notice step 3: left and right were both equal to 3. Because the condition was left <= right, the loop ran one last time, computed mid = 3, and found the target.

Trace 2: The Single-Element Trap (`nums = [5]`, `target = 5`)

This is the exact test case that exposes the left < right bug in closed intervals:

Single Element Edge Case Comparison· EDGE CASE

2 steps

Condition Used	Initial left	Initial right	Does loop run?	Result	Status
while (left < right)	0	0	No (0 < 0 is false)	Returns -1	❌ Bug: Failed to find 5
while (left <= right)	0	0	Yes (0 <= 0 is true)	Returns 0	✅ Correct: Found at index 0

Why Must We Use `mid + 1` and `mid - 1`?

Because nums[mid] has already been evaluated by if (nums[mid] === target). Since we know nums[mid] is not the target, keeping mid inside our active search space is wasteful.

More critically, if you write left = mid or right = mid with while (left <= right), you introduce an infinite loop. When right - left === 1, integer division rounds down, causing mid to equal left. If your code sets left = mid, left never changes, and the loop runs forever.

Template 2: The Half-Open Interval (`left < right`)

In algorithms where you search for boundary transitions, insertion points (LeetCode 35: Search Insert Position), or monotonic conditions, the half-open interval [left, right) is frequently preferred.

The Invariant Rules

Initial State: left = 0, right = nums.length (Notice: not length - 1!)
Loop Condition: while (left < right)
Left Update: left = mid + 1 (because mid was checked and ruled out)
Right Update: right = mid (because right is exclusive, setting right = mid excludes mid from the next round!)

lowerBoundSearch.ts· TypeScript

Trace Code

export function searchInsert(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length; // Range is [0, nums.length)

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);

    if (nums[mid] < target) {
      left = mid + 1; // Target is strictly in [mid + 1, right)
    } else {
      right = mid; // Target could be at mid, so keep mid as exclusive upper bound [left, mid)
    }
  }

  // When loop exits, left === right, representing the exact insertion index
  return left;
}

Why Is `right = nums.length`?

Because the interval is half-open [left, right), the value at right is never examined. If the target is greater than every element in the array, its correct insertion point is at index nums.length. If you initialized right = nums.length - 1, the search space could never consider index nums.length as a valid answer.

Why Is the Update `right = mid` Instead of `mid - 1`?

In half-open intervals, [left, mid) excludes mid. Therefore, setting right = mid already discards nums[mid] from future consideration without skipping any candidates between left and mid - 1.

Trace 3: Target Missing (`nums = [1, 3, 5, 7]`, `target = 4`)

Let us trace how the half-open boundary converges on the insertion point:

Half-Open Interval Execution Trace: Insertion Search· TEMPLATE 2

4 steps

Step	left	right	mid	nums[mid]	Evaluation	Next Search Interval
0	0	4	—	—	Initial range [0..4)	[1, 3, 5, 7]
1	0	4	2	5	5 >= 4	right = mid = 2. New interval [0..2) ([1, 3])
2	0	2	1	3	3 < 4	left = mid + 1 = 2. New interval [2..2)
3	2	2	—	—	left === right	Loop terminates. Return `left = 2`

At step 3, left === right === 2. The value 4 should be inserted at index 2 (between 3 and 5). The pointers naturally locked onto the exact insertion position.

The Two Silent Killers of Binary Search

Even when developers memorize loop conditions, two subtle traps cause real-world outages.

1. The 32-Bit Integer Overflow

In languages with fixed-width 32-bit signed integers (such as Java, C++, and Go), calculating the midpoint with (left + right) / 2 is a bug waiting to happen:

// ❌ DANGEROUS: Can overflow signed 32-bit integer
int mid = (left + right) / 2;

If left and right are both large (for example, in an array with $1.5 \times 10^9$ elements or when performing binary search over a large numeric domain), their sum exceeds $2^{31} - 1$ ($2,147,483,647$). In two's complement arithmetic, the sum overflows into a negative number, resulting in a negative index and an immediate ArrayIndexOutOfBoundsException.

The fix is mathematically identical but physically safe from overflow:

// ✅ SAFE: Subtract first, then divide, then add
const mid = left + Math.floor((right - left) / 2);

Because right >= left, the difference right - left is always non-negative and strictly smaller than right. It can never overflow.

2. The Midpoint Truncation Trap

When you update pointers using left = mid (common in searches for upper bounds or peak elements), integer truncation can freeze your loop:

Consider left = 2 and right = 3:

// Integer division rounds DOWN:
const mid = Math.floor((2 + 3) / 2); // mid = 2

// If your logic dictates:
if (condition) {
  left = mid; // left stays 2!
}

On the next iteration, left is still 2 and right is still 3. The midpoint is computed as 2 again. The code enters an unbreakable infinite loop.

The Rule:

If you use left = mid, you must bias the midpoint calculation upwards by rounding up: const mid = left + Math.floor((right - left + 1) / 2);
Alternatively, stick to the standard invariants where left = mid + 1 and right = mid - 1 are used.

The Binary Search Decision Cheat Sheet

Use this reference table to select the correct template for your problem:

Binary Search Template Matrix· CHEAT SHEET

9 steps

Feature	Closed Interval [left, right]	Half-Open Interval [left, right)
Primary Goal	Find an exact value match	Find boundary, insertion point, or lower bound
Initial `left`	0	0
Initial `right`	nums.length - 1	nums.length
Loop Condition	while (left <= right)	while (left < right)
Target < nums[mid]	right = mid - 1	right = mid
Target > nums[mid]	left = mid + 1	left = mid + 1
Termination State	left > right (Search space empty)	left === right (Pointers converged on boundary)
Return on Match	Return mid immediately inside loop	Return left (or right) after loop exits
Return on Failure	Return -1	Return left (insertion index)

BINARY SEARCH FAQ

Frequently Asked Questions

Infinite loops occur when the search space does not shrink during an iteration. This happens when integer division rounds down (mid === left) and the code updates left = mid. Because left never changes value, the loop condition remains true indefinitely. To fix this, always use left = mid + 1 or bias your midpoint upward when using left = mid.

Step Through Binary Search in Real Time

Reading about pointers on a page cannot replace watching them navigate memory on real test cases.

Explore how binary search boundaries shrink across different variations in TraceDSA's interactive workbench:

Step Through Standard Binary Search — Watch the inclusive brackets contract frame by frame.
Trace Search Insert Position — Observe the half-open interval lock onto the insertion point.
Inspect Search in Rotated Sorted Array — See how inflection points split the binary search condition.
Explore Minimum in Rotated Sorted Array — Watch boundary convergence on unsorted halves.
Visualize Koko Eating Bananas — Step through binary search applied to an answer domain.

When you can visualize where left and right sit in physical memory, binary search stops being a source of off-by-one anxiety. The boundaries become obvious.

INTERACTIVE PRACTICE

Ready to trace these algorithms step by step?

Open the TraceDSA visualizer to inspect pointer movements, stack frames, and array boundaries across 96+ LeetCode problems.

Trace Two Sum Browse Directory