Introduction

Most binary search bugs are not about the idea of halving the search range. They are about boundaries, loop invariants, and deciding exactly what answer you want. A correct binary search starts by defining the search condition clearly, such as exact match, first occurrence, last occurrence, or first value meeting a predicate.

Start With One Precise Contract

If the problem is "find whether target exists," the code can return as soon as it finds a match. But many real interview and production problems are slightly different:

• first occurrence of a duplicated value
• last occurrence of a duplicated value
• insertion position
• smallest value greater than or equal to target
• first index where a condition becomes true

These are all binary-search problems, but they need different update rules.

A standard exact-match implementation is:

1
2def binary_search(nums, target):
3    left, right = 0, len(nums) - 1
4
5    while left <= right:
6        mid = left + (right - left) // 2
7        if nums[mid] == target:
8            return mid
9        if nums[mid] < target:
10            left = mid + 1
11        else:
12            right = mid - 1
13
14    return -1
15
16
17print(binary_search([1, 3, 5, 7, 9], 7))

That version is fine for exact lookup, but it does not guarantee the first or last matching index when duplicates exist.

Handle Duplicates With Purpose

Suppose the requirement is "find the first occurrence." Then you should not stop immediately on equality. You must keep searching left.

1
2def first_occurrence(nums, target):
3    left, right = 0, len(nums) - 1
4    answer = -1
5
6    while left <= right:
7        mid = left + (right - left) // 2
8        if nums[mid] >= target:
9            if nums[mid] == target:
10                answer = mid
11            right = mid - 1
12        else:
13            left = mid + 1
14
15    return answer
16
17
18print(first_occurrence([1, 2, 2, 2, 4], 2))

For the last occurrence, reverse the bias and keep searching right after a match.

That is why many binary-search problems feel tricky. The skeleton is small, but the boundary decisions depend on the exact contract.

Use Binary Search on Predicates, Not Only Values

A powerful way to think about binary search is that it finds a transition point in a monotonic predicate. For example, imagine an array where the condition nums[i] >= target is false for a while and then true forever. Binary search can find the first true position.

1
2def lower_bound(nums, target):
3    left, right = 0, len(nums)
4
5    while left < right:
6        mid = left + (right - left) // 2
7        if nums[mid] < target:
8            left = mid + 1
9        else:
10            right = mid
11
12    return left
13
14
15print(lower_bound([1, 2, 2, 4, 5], 2))
16print(lower_bound([1, 2, 2, 4, 5], 3))

This style is extremely useful because many search problems are really about finding the boundary where a condition flips.

Common Bug Sources

Binary search bugs usually come from one of four places:

• wrong loop condition such as left < right versus left <= right
• updating the wrong boundary after inspecting mid
• using a midpoint rule inconsistent with the loop invariant
• not defining clearly what should happen on equality

The classic overflow-safe midpoint formula left + (right - left) // 2 is also worth remembering, especially in languages with fixed-size integers.

Debug by Writing the Invariant

One of the best ways to debug binary search is to write down what you know is true about the range at every loop iteration.

For example, in a lower-bound search you might say:

• everything before left is definitely too small
• everything at or after right is a candidate answer

Once that invariant is clear, the boundary updates become much easier to reason about.

Common Pitfalls

A common mistake is copying a binary-search template without checking whether the problem needs exact match, first match, or boundary search.

Another mistake is returning immediately on equality even when the requirement is first or last occurrence among duplicates.

People also often mix half-open intervals and closed intervals in the same function. Pick one interval style and keep it consistent.

Finally, binary search only works when the search space is monotonic with respect to the condition you are testing. If that property is missing, the algorithm is not valid.

Summary

• Binary search problems differ mainly in the exact boundary or match condition you need.
• Duplicates require deliberate handling if the answer must be first or last occurrence.
• Many search tasks are easier to frame as finding the first true position of a monotonic predicate.
• Most bugs come from boundary updates and unclear loop invariants.
• Define the contract first, then choose the binary-search variant that matches it.