Binary Search: the off-by-one minefield

Everyone has a binary search story. Mine involved a phone interview, a sorted array, and a loop that ran forever because I wrote right = mid instead of right = mid - 1. I knew the algorithm. I'd used it dozens of times. And I still got the boundary wrong under pressure. That's the thing about binary search — the idea is trivial, the implementation is not.

The problem (LeetCode 704): given a sorted array of integers and a target, return the index of the target or -1 if it doesn't exist. The constraint is explicit — O(log n) runtime required.

Reading the constraints

The constraints here are minimal, but they still shape your approach.

1 <= nums.length <= 10^4. The lower bound means no empty array to worry about. The upper bound (10,000 elements) is small enough that even a linear scan would finish in microseconds on modern hardware. But the problem says O(log n), so that's the bar.

-10^4 < nums[i], target < 10^4. Values are bounded, no overflow concerns on the array elements themselves. That said, the mid-point calculation (lo + hi) still overflows in languages with fixed-width integers if both are near Int32.MaxValue — more on that below.

All integers are unique. This eliminates any ambiguity about which index to return if duplicates were present. One match, one answer.

Array is sorted ascending. This is what makes binary search applicable at all. The sorted property is the invariant you exploit — every step, you know which half the target must be in. Without it, you're back to linear scan.

Brute force: O(n)

The naive approach: scan every element in order. When you hit the target, return its index. If you exhaust the array, return -1.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == target) return i;
        }
        return -1;
    }
}

This works. It ignores the sorted property entirely and violates the O(log n) requirement. Worst case is when the target is at the last position or absent, requiring a full pass through all n elements. Time O(n), space O(1).

The problem forbids this. But it's a useful baseline — if the array weren't sorted, linear scan is exactly what you'd reach for.

Binary search (iterative): O(log n)

The idea: given a sorted array, you can find any target in O(log n) time by repeatedly halving the search space. At each step you look at the middle element. If it matches, you're done. If the target is smaller, it must be in the left half. If larger, the right half. Discard the losing half and repeat.

Ten iterations handles 1,024 elements. Twenty handles a million. The O(log n) guarantee is real and it's dramatic.

Here is the template I reach for every time:

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
 
        while lo <= hi:
            mid = lo + (hi - lo) // 2
 
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
 
        return -1

public class Solution {
    public int Search(int[] nums, int target) {
        int lo = 0, hi = nums.Length - 1;
 
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
 
            if (nums[mid] == target)   return mid;
            if (nums[mid] < target)    lo = mid + 1;
            else                       hi = mid - 1;
        }
 
        return -1;
    }
}

lo <= hi. mid + 1 and mid - 1. The loop exits cleanly when lo > hi, meaning the search space is empty. At that point the target is confirmed absent, and -1 is correct.

Tracing through the first example

nums = [-1, 0, 3, 5, 9, 12], target = 9. Let me walk it step by step.

In prose:

lo=0, hi=5  ->  mid=2  ->  nums[2]=3  <  9  ->  lo=3
lo=3, hi=5  ->  mid=4  ->  nums[4]=9  == 9  ->  return 4

Two iterations. Array has 6 elements. You started with 6 candidates, cut to 3 in the right half, then landed on the answer.

Tracing the absent target

nums = [-1, 0, 3, 5, 9, 12], target = 2. The algorithm has to confirm absence without revisiting any element.

lo=0, hi=5  ->  mid=2  ->  nums[2]=3  >  2  ->  hi=1
lo=0, hi=1  ->  mid=0  ->  nums[0]=-1 <  2  ->  lo=1
lo=1, hi=1  ->  mid=1  ->  nums[1]=0  <  2  ->  lo=2
lo=2, hi=1  ->  lo > hi  ->  exit
return -1

Three iterations, six elements. Clean exit. No element was revisited. The absent target produces lo > hi, the loop terminates, and -1 is correct.

Why lo <= hi and not lo < hi

The <= vs < question trips people up because both can work — they just work differently, and mixing rules from one into the other produces bugs.

With lo <= hi, the loop runs as long as there is at least one element left to examine. When lo == hi, you still have one candidate. The loop body checks it. If it's not the target, you push lo past hi (or pull hi past lo) and exit. Every element gets exactly one shot.

With lo < hi, the loop exits when lo == hi, leaving one element unexamined. That means you must check nums[lo] after the loop. This is fine if you always remember to do it. In my experience, you don't always remember.

The lo <= hi template is self-contained. The loop handles every element, including the singleton case. No post-loop check needed. I picked it years ago and I've never switched.

The mid calculation

mid = lo + (hi - lo) // 2

Not (lo + hi) // 2. In Python this rarely matters because integers don't overflow. In C# (and Java, C++) it does matter: lo + hi can overflow int if both are near Int32.MaxValue. lo + (hi - lo) / 2 is mathematically equivalent but safe — hi - lo is always non-negative and bounded by the array length.

Habit pays off here. Write it the safe way and you never have to think about it again.

What happens on a miss

This is where most implementations go wrong.

When nums[mid] < target, you know the target is strictly to the right of mid. The next search space starts at mid + 1. If you write lo = mid, you include mid in the next iteration even though you've already eliminated it — and if lo == hi == mid, you're stuck in an infinite loop.

When nums[mid] > target, symmetric reasoning: the next search space ends at mid - 1. Write hi = mid - 1.

Always exclude mid on a miss. That's the invariant. Violate it and you get infinite loops or missed elements.

The lo < hi boundary-finding variant

This template exists, it's valid, and you'll see it in editorial solutions for boundary problems. The full form for exact match:

lo, hi = 0, len(nums) - 1
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid          # NOT mid - 1
return nums[lo] if nums[lo] == target else -1

public class Solution {
    public int Search(int[] nums, int target) {
        int lo = 0, hi = nums.Length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < target) lo = mid + 1;
            else                    hi = mid;   // NOT mid - 1
        }
        return nums[lo] == target ? lo : -1;
    }
}

The key difference: on the nums[mid] >= target branch, you write hi = mid instead of hi = mid - 1. This is safe because lo < hi guarantees mid < hi, so hi = mid does shrink the window. The loop exits with lo == hi, and you check that one remaining element explicitly after the loop.

Why does this template exist? It's useful when you're searching for a boundary — the leftmost index where some condition first holds — rather than an exact match. The lo < hi loop exits pointing at the answer instead of stepping past it.

For this problem specifically, lo <= hi is cleaner and I'd use it. But you should know both, because boundary-finding problems need this form and interview problems lean heavily on that.

Binary search (recursive): O(log n)

It's also possible to implement binary search recursively. The base case is an empty search space (lo > hi); the recursive case is the same three-way branch.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        def bs(lo, hi):
            if lo > hi:
                return -1
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                return bs(mid + 1, hi)
            return bs(lo, mid - 1)
        return bs(0, len(nums) - 1)

public class Solution {
    public int Search(int[] nums, int target) => Bs(nums, target, 0, nums.Length - 1);
 
    private int Bs(int[] nums, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target)  return Bs(nums, target, mid + 1, hi);
        return Bs(nums, target, lo, mid - 1);
    }
}

O(log n) time, O(log n) stack space. The call depth is at most log2(10^4) ≈ 14 frames for this problem's constraints — not a stack overflow risk. But there's no practical reason to prefer this over the iterative version. The iterative form is shorter, faster, and has O(1) space. I'd only write this if a problem naturally decomposed recursively (e.g., recursive data structures). Here it's a tutorial device.

Complexity comparison

Edge cases that actually matter

Single element, target present. nums = [5], target = 5. lo=0, hi=0. mid=0. nums[0] == 5. Return 0. The <= in while lo <= hi is precisely what makes the singleton work — the loop body runs once for lo == hi.

Single element, target absent. nums = [5], target = 3. mid=0. nums[0]=5 > 3. hi = -1. Now lo=0 > hi=-1 — the condition fails on the very next check, loop exits. Return -1.

Target smaller than all elements. nums = [3, 5, 9], target = 1. The first mid gives nums[mid] > 1, so hi drops below lo after one step. Return -1. No special case needed.

Target larger than all elements. nums = [3, 5, 9], target = 11. Every mid compares less than the target, so lo climbs until it exceeds hi. Return -1. Symmetric to the above.

Target at index 0. nums = [1, 2, 3], target = 1. The mid calculation eventually hits index 0 through normal narrowing — no special handling required.

Target at the last index. nums = [1, 2, 3], target = 3. Symmetric. The right half keeps getting selected until mid lands on the last index.

None of these require special handling. The lo <= hi loop absorbs every one of them because the invariant holds: when the search space becomes empty, lo > hi, and the loop exits cleanly.

Pattern recognition and when to reach for this

Binary search triggers when you see a sorted structure and a search task. The clearest signals:

• The input is sorted (ascending or descending) or monotonically ordered in some way.
• The problem asks for O(log n) explicitly.
• You're searching for an element, a position, or a boundary value.

The less obvious triggers come up in harder problems: searching on the answer space (binary search on integers, not on the array), or problems where the search space is implicitly monotone even if the array isn't (e.g., rotated arrays retain the sorted property in each half — you just have to figure out which half).

The underlying mental model is: "I can always eliminate half the remaining candidates in one comparison." That's the invariant that makes O(log n) possible. As long as you can express your condition in a form that partitions the space that cleanly, binary search applies.

Where this series goes from here

Binary search on a one-dimensional sorted array is the base pattern. The next articles apply the same core idea to problems that disguise the sorted structure: a matrix that happens to be searchable as a flattened array, a rotated array where the sorted property is preserved in pieces, and a range of integers where you binary-search on the answer itself.

Related problems worth working through next:

• Search a 2D Matrix (74) — the matrix rows are sorted and the last element of each row is less than the first of the next. The whole matrix can be treated as one sorted sequence, then binary-searched with index arithmetic.
• Find Minimum in Rotated Sorted Array (153) — sorted array, then rotated. Binary search still applies; the split condition changes from "compare to target" to "compare to the right boundary."
• Search in Rotated Sorted Array (33) — find a target in a rotated array. You binary-search on which half is still sorted, then recurse into it.
• Search Insert Position (35) — find where to insert a value in a sorted array. The lo < hi boundary template handles this more naturally than lo <= hi.
• First Bad Version (278) — binary search on a range of integers, not an array. Same template, different search space.