Imagine you are looking for a word in a physical dictionary. You would not start from page one and flip through every page until you find it. Instead, you would open the dictionary somewhere in the middle, see if your word comes before or after that page, and then repeat the process in the relevant half. Within seconds, you narrow down thousands of pages to exactly the one you need.

This simple idea, repeatedly halving the search space, is the essence of binary search. It is one of the most powerful and frequently used techniques in computer science, appearing in everything from database indexing to machine learning algorithms.

What makes binary search tricky is not the basic concept. The tricky part is recognizing when to use it and handling the edge cases correctly. Off-by-one errors haunt even experienced developers. Master the templates in this chapter, and you will have a reliable framework for solving any binary search problem.

What Is Binary Search?

Binary search is a search algorithm that finds the position of a target value within a sorted collection. Instead of checking each element one by one, it compares the target with the middle element and eliminates half of the remaining elements with each comparison.

The key requirement is that the search space must have a monotonic property. In the simplest case, this means the array is sorted. But more generally, it means there is some condition that is false for all elements on one side of a boundary and true for all elements on the other side.

In this diagram, we are searching for 9. We check the middle element (7), find that 9 is greater, so we eliminate the left half (red) and continue searching in the right half (blue). The target (green) is found in the next iteration.

Why O(log n)?

With each comparison, binary search eliminates half the remaining elements. If you start with n elements:

We stop when only 1 element remains: n/2^k = 1, which gives k = log₂(n).

For an array of 1 billion elements, binary search needs at most 30 comparisons. Linear search might need 1 billion.

When to Use Binary Search

Binary search is the right tool when your problem has these characteristics:

1. The search space is sorted or has a monotonic property

The classic case is a sorted array. But the search space could also be a range of possible answers where you can determine if an answer is "too small" or "too big."

2. You can eliminate half the search space with each check

Given any point in the search space, you must be able to determine which half contains the answer. This is the key insight that makes binary search work.

3. Random access is available

You need O(1) access to any element in the search space. This is why binary search works on arrays but not on linked lists.

Here are common problem types where binary search excels:

Binary Search Variants and Templates

The power of binary search comes from its variants. While the core idea is the same, small changes in the template let you solve very different problems. Let us go through each variant with a reusable template.

Variant 1: Standard Binary Search (Find Exact Target)

This is the classic version. Given a sorted array, find if a target exists and return its index.

Template:

Key Points:

Example Walkthrough:

Variant 2: Find Lower Bound (First Occurrence)

When duplicates exist, standard binary search might return any occurrence. This variant finds the first (leftmost) occurrence of the target.

Template:

Key Points:

Example Walkthrough:

Variant 3: Find Upper Bound (Last Occurrence)

This variant finds the last (rightmost) occurrence of the target.

Template:

Key Points:

Example Walkthrough:

Variant 4: Find First Element Greater Than Target

Sometimes you need the first element strictly greater than a given value. This is useful for insertion points and range queries.

Template:

Example Walkthrough:

Variant 5: Find First Element Greater Than or Equal To Target

This is equivalent to finding the insertion point if you were to insert the target while maintaining sorted order.

Template:

This is identical to the lower bound template. The difference is in how you use the result.

Variant 6: Binary Search on Answer Space

This is perhaps the most powerful variant. Instead of searching in an array, you search in a range of possible answers. The key insight is that if a certain value works as an answer, then all values more lenient than it also work.

Template:

Key Points:

Example: Minimum Capacity to Ship Packages

Given packages with weights and a required number of days, find the minimum ship capacity needed.

Choosing the Right Template

Here is a quick reference for choosing the correct variant:

Example Walkthrough: Count Elements in Range

Let us solve a problem that combines multiple variants. Given a sorted array with duplicates, count how many elements fall within a range [lo, hi].

Problem: Given nums = [1, 2, 2, 3, 3, 3, 4, 5], count elements in range [2, 3].

Solution: Find the first element >= 2 and the first element > 3. The count is the difference of their indices.

Common Mistakes and How to Avoid Them

Mistake 1: Off-by-One Errors in Loop Condition

The most common source of bugs is mixing up left <= right and left < right.

Mistake 2: Integer Overflow in Mid Calculation

Mistake 3: Infinite Loop from Wrong Update

When using left = mid, use mid = left + (right - left + 1) / 2 (round up) to avoid infinite loops.

Mistake 4: Wrong Initial Bounds

Mistake 5: Not Handling Edge Cases

Always consider: