Binary Search Off by One Errors: A Boundary-Safe Guide

Binary search off by one errors usually come from an unclear search space, not from the midpoint formula. You can prevent most of them by choosing one interval convention, stating its invariant, and making every boundary update preserve that invariant.

This guide uses a half-open interval and applies it to [LeetCode 35: Search Insert Position). The same reasoning works for exact matches, lower bounds, upper bounds, and other monotonic searches.

Why Binary Search Produces So Many Off-by-One Errors#

Most binary search bugs begin when left and right do not have precise meanings.

Consider a search with left = 0 and right = len(nums) - 1. Does right remain under consideration? If it does, the interval is closed. The loop usually needs left <= right.

Now consider right = len(nums). That value is outside the array, so it cannot represent an index you plan to inspect. It usually marks the excluded end of a half-open interval. The loop normally uses left < right.

Problems appear when you combine one interpretation with updates from the other:

left, right = 0, len(nums)

while left <= right:
    mid = left + (right - left) // 2

Here, right begins at len(nums), but left <= right allows mid to become len(nums). Accessing nums[mid] would then fail.

The broader issue is that “binary search” describes several related searches.

• Exact match: Find any index whose value equals the target.
• Lower bound: Find the first index whose value is greater than or equal to the target.
• Upper bound: Find the first index whose value is greater than the target.
• Insertion point: Find the boundary where a target can be inserted while preserving order.
• First true: Find the first position where a monotonic condition becomes true.

These goals do not use equality in the same way. An exact-match search can return as soon as it finds equality. A lower-bound search cannot. It must keep searching left because an earlier equal value may exist.

That is why memorising isolated rules such as left = mid + 1 is unreliable. The update may be correct, but only if you can explain which positions it removes and why none of them can contain the answer.

A binary search invariant gives each variable a stable meaning. Before every iteration, you should know:

1. Which positions have already been ruled out.
2. Which positions remain unresolved.
3. Where the answer is allowed to be.
4. Why the next update makes the unresolved region smaller.

If you can answer those points, the boundary code follows from the argument.

Choose an Interval Invariant Before Writing Code#

Choose either a closed interval or a half-open interval before you calculate mid.

Closed interval: [left, right]#

A closed interval includes both boundaries. Every index from left through right remains under consideration.

For an exact-match search:

left, right = 0, len(nums) - 1

while left <= right:
    mid = left + (right - left) // 2

    if nums[mid] < target:
        left = mid + 1
    elif nums[mid] > target:
        right = mid - 1
    else:
        return mid

return -1

The pieces match:

• Initial interval: [0, len(nums) - 1]
• Loop condition: left <= right
• Midpoint: left + (right - left) // 2
• Discard left side through mid: left = mid + 1
• Discard right side through mid: right = mid - 1
• Termination: left > right, so the interval is empty
• Return on failure: -1

When nums[mid] < target, sorted order proves that indices from left through mid cannot contain the target. The next possible index is mid + 1.

When nums[mid] > target, indices from mid through right cannot contain the target. The new rightmost possibility is mid - 1.

Half-open interval: [left, right)#

A half-open interval includes left but excludes right. The unresolved array indices begin at left and stop before right.

For an exact-match search:

left, right = 0, len(nums)

while left < right:
    mid = left + (right - left) // 2

    if nums[mid] < target:
        left = mid + 1
    elif nums[mid] > target:
        right = mid
    else:
        return mid

return -1

Its matching pieces are:

• Initial interval: [0, len(nums))
• Loop condition: left < right
• Midpoint: left + (right - left) // 2
• Discard through mid on the left: left = mid + 1
• Keep indices before mid on the right: right = mid
• Termination: left == right, so [left, right) is empty
• Return on failure: -1

The important difference is right = mid, not right = mid - 1. Because right is excluded, assigning mid to it already removes mid from the next interval.

Use one template consistently in your own code. You should still be able to read the other during an interview or code review. Do not translate individual lines between them without translating the invariant too.

For the rest of this guide, the chosen binary search invariant is half-open. It fits lower-bound binary search cleanly and allows len(nums) to represent a valid insertion point.

A Boundary-Safe Lower-Bound Template in Python#

A lower-bound search finds the first index i for which nums[i] >= target.

The array must be sorted. The condition nums[i] >= target is then monotonic: it is false for some prefix and true for the remaining suffix.

def lower_bound(nums, target):
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left

Read each line through the invariant:

• Every index before left has a value less than target.
• Every array index at or after right has a value greater than or equal to target.
• The unresolved array indices are in [left, right).
• The answer boundary remains between left and right, inclusive.

The last point is subtle. right is excluded from array inspection, but it is still a possible answer boundary. That is what lets the function return len(nums).

If nums[mid] < target, then mid cannot be the lower bound. Neither can any earlier index. Sorted order lets you set:

left = mid + 1

If nums[mid] >= target, then mid may be the first qualifying index. You must preserve it as a possible answer:

right = mid

You do not return immediately on equality. Doing so would find an occurrence, not necessarily the first occurrence.

Why right = len(nums) is valid#

len(nums) is not used as an array index. It is an exclusive boundary and a valid insertion position after the final element.

With left < right, the midpoint always satisfies:

left <= mid < right

Since right begins at len(nums), mid always remains a valid array index whenever the loop runs.

The template also handles binary search edge cases without separate branches:

• Empty array: left and right both start at 0. The loop does not run. The function returns 0.
• One element below the target: left advances to 1, which is the insertion point after the element.
• One element at or above the target: right moves to 0, so the result is 0.
• Duplicates: Equality moves right leftward, producing the first matching index.
• Target below every value: The result is 0.
• Target above every value: The result is len(nums).

This is a boundary search, not merely an equality search. Its return value is always a valid insertion position from 0 through len(nums).

Worked Example: Search Insert Position#

Search Insert Position asks you to return the index of a target in a sorted array, or the index where it should be inserted.

That is exactly a lower-bound search. You need the first index whose value is greater than or equal to the target.

Use:

nums = [1, 3, 5, 6]

Target is present#

For target = 5:

[0, 4) -> mid 2 -> nums[2] is 5 -> right = 2
[0, 2) -> mid 1 -> nums[1] is 3 -> left = 2
stop at left = right = 2

Equality does not cause an immediate return. The search keeps index 2 as a candidate and checks whether an earlier valid position exists.

The answer is 2.

Target is missing between values#

For target = 2:

[0, 4) -> mid 2 -> nums[2] is 5 -> right = 2
[0, 2) -> mid 1 -> nums[1] is 3 -> right = 1
[0, 1) -> mid 0 -> nums[0] is 1 -> left = 1
stop at left = right = 1

Index 1 is the boundary between values below 2 and values at least 2.

Target is smaller than every value#

For target = 0:

[0, 4) -> mid 2 -> right = 2
[0, 2) -> mid 1 -> right = 1
[0, 1) -> mid 0 -> right = 0
stop at 0

No index is ruled out on the left. The insertion position is 0.

Target is larger than every value#

For target = 7:

[0, 4) -> mid 2 -> left = 3
[3, 4) -> mid 3 -> left = 4
stop at 4

The result equals len(nums). That is a valid insertion position after the final element.

Complete Python solution#

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums)

        while left < right:
            mid = left + (right - left) // 2

            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid

        return left

Each iteration removes a substantial part of the unresolved interval. The time complexity is O(log n). The algorithm stores only boundary and midpoint variables, so its auxiliary space complexity is O(1).

The Boundary Bugs to Check First#

When binary search fails, check whether the loop condition, updates, and return value belong to the same interval convention.

Mixing left < right with left <= right#

Use left <= right when both endpoints are valid candidates in a closed interval.

Use left < right when right is excluded in a half-open interval.

Do not choose the condition based on appearance. Derive it from when your interval becomes empty:

• [left, right] is empty when left > right.
• [left, right) is empty when left == right.

Using right = mid - 1 in a half-open template#

Suppose nums[mid] >= target during a lower-bound search. Index mid may be the answer.

This update is wrong:

right = mid - 1

It removes both mid and the new excluded boundary position. You may skip the correct lower bound.

The half-open update is:

right = mid

Because the next interval excludes right, mid will not be inspected again. It remains a possible answer boundary.

Failing to remove mid#

An update must make the interval strictly smaller.

This can loop forever:

left = mid

With a floor midpoint, mid can equal left. For an interval such as [3, 4), the midpoint is 3. Assigning left = mid changes nothing.

Use left = mid + 1 when the condition proves that mid cannot be the answer.

Some binary searches deliberately use left = mid. Those usually need an upper-biased midpoint:

mid = left + (right - left + 1) // 2

The bias and the updates form one design. Do not copy the midpoint independently.

Treating the return value as an array index#

A lower bound may return len(nums). This is safe:

index = lower_bound(nums, target)

This is not always safe:

value = nums[lower_bound(nums, target)]

Check index < len(nums) before indexing. If you need an exact match, also verify nums[index] == target.

Assuming the input is nonempty#

Initialising a closed interval with right = len(nums) - 1 produces -1 for an empty array. That can still work if the loop condition is correct, but later indexing may not.

The half-open template makes empty input explicit: [0, 0) is already empty.

Returning early with duplicates#

Returning when nums[mid] == target is correct for “find any occurrence.” It is incorrect for lower bound or “find the first occurrence.”

With duplicates, define the requested boundary before coding:

• First nums[i] >= target: lower bound.
• First nums[i] > target: upper bound.
• First equal position: lower bound followed by an equality check.
• Last equal position: upper bound minus one, followed by validation.

The duplicate policy belongs in the invariant, not in a patch after the loop.

How to Test Binary Search Without Guessing#

Test binary search by covering interval shapes and postconditions, not by collecting random arrays.

A compact lower-bound test set can include:

assert lower_bound([], 4) == 0
assert lower_bound([5], 5) == 0
assert lower_bound([5], 2) == 0
assert lower_bound([5], 8) == 1

assert lower_bound([1, 3, 5, 7], 5) == 2
assert lower_bound([1, 3, 5, 7], 4) == 2
assert lower_bound([1, 3, 5, 7], 9) == 4

assert lower_bound([1, 3, 5], 3) == 1
assert lower_bound([1, 3, 5], 0) == 0
assert lower_bound([1, 2, 2, 2, 4], 2) == 1

This covers empty, singleton, even-length, odd-length, duplicate, present, and absent cases.

For a binary search dry run, record the state mechanically. Here is nums = [1, 2, 2, 2, 4] with target = 2:

The loop terminates at index 1.

Example outputs are useful, but they are not enough. Verify two properties separately.

Termination#

For every iteration where left < right:

• mid < right, so right = mid decreases right.
• mid >= left, so left = mid + 1 increases left.

The interval length right - left therefore decreases. It cannot decrease forever without reaching zero.

Postcondition#

When the loop ends, left == right.

The invariant tells you:

• Every index before left contains a value below the target.
• Every array index at or after left contains a value at least equal to the target.

Therefore, left is the first qualifying index. This proves the return value without relying on a particular example.

How to Explain the Invariant in an Interview#

State the search space and postcondition before you write the loop.

A concise script is:

I’ll use a half-open interval. Indices before left are known to be below the target. Indices at or after right are known to be at least the target. The unresolved indices are [left, right), and I’ll stop when that interval is empty.

Then narrate the updates by explaining what they prove:

If nums[mid] is below the target, sorted order rules out mid and everything to its left, so I move left to mid + 1.

Otherwise, mid could be the first valid position, so I keep it as a candidate by moving right to mid.

That explanation is stronger than reading if, else, and assignment statements aloud. It shows why the code is correct and gives you a way to recover if you forget an update.

Before finishing, state the postcondition:

At termination, left equals right. Everything before that boundary is too small, and everything from that boundary onward qualifies. So the boundary is the lower bound and the required insertion position.

For broader practice, use the binary search pattern hub. Compare this boundary search with [LeetCode 704: Binary Search), which asks for an exact match, and LeetCode 34, Find First and Last Position of Element in Sorted Array, which requires explicit duplicate boundaries.

The template matters. The invariant matters more. If every update preserves a meaning you stated before coding, binary search boundaries become something you can derive instead of something you have to remember.