Pattern 1: Binary Search

The idea is like looking up a name in a phone book: you don't start on the first page — you open it in the middle and decide which way to go. Each decision eliminates half of what's left.

Tried it? The "obvious" solution is to walk the array from start to end — O(n). It works, but it ignores the most valuable piece of information in the statement: the array is sorted. The theory below shows how the order brings this down to O(log n).

The theory: exploiting the order

In a sorted array, the middle value tells you a lot. If you're looking for target and the middle is smaller than it, then target — if it exists — can only be to the right of the middle (everything on the left is even smaller). You just discarded half of the array without looking. Symmetrically if the middle is larger.

left = 0, right = n - 1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target → found
    if nums[mid]  < target → the target is on the right: left = mid + 1
    if nums[mid]  > target → the target is on the left: right = mid - 1
not found → -1

Follow the active interval [left..right] shrinking by half at each step, with mid in the center:

Why is it O(log n)? (the full justification)

The key question: how many times can you divide n by 2 until just 1 element remains? That's the definition of log₂(n):

• n = 8 → 4 → 2 → 1: 3 steps (log₂ 8 = 3)
• n = 1,000,000 → ... → 1: ~20 steps (2²⁰ ≈ 1 million)

Each loop iteration discards half of the remaining space and does only O(1) work (one comparison, adjusting a pointer). Since the number of iterations is log₂(n), the total is O(log n) time and O(1) space. It's not "somewhat faster" — it's exponentially better than linear search.

The classic trap: the boundary details

Binary search is easy to understand and easy to get wrong in the details. Three points that trip up a lot of people:

1. left <= right or left < right? With right = n-1 (a valid index), use <= — otherwise you don't check the last element when left == right.
2. mid + 1 / mid - 1? Since nums[mid] was already tested, exclude it from the next interval. Forgetting the ±1 causes an infinite loop.
3. Overflow of mid? In languages with fixed-size integers, (left + right) can overflow; left + (right - left) // 2 avoids that. (In the course's Python/JS it's not a problem, but it's good to know for Java/C++ interviews.)

Edit the code and force the bugs (swap mid + 1 for mid) to watch the infinite loop get cut off by the step limit:

Binary search is more than "finding a value"

The real power comes when you realize that binary search works in any monotonic space — where there's a boundary "before it no, from it on yes". Finding the first element ≥ x, the last ≤ x, or even "the smallest speed that gets the task done" (binary search on the answer) — it's all binary search with the same backbone. You'll see this in the synthesis and on the exam.

Summary

• Binary search needs order; it looks at the middle and discards half per step.
• O(log n) because n is divided by 2 until it reaches 1 (log₂ n steps), each O(1).
• Watch out for boundaries: <=, mid ± 1, overflow of mid.
• Generalizes to boundaries and "search on the answer" — any monotonic space.

Next lesson: what about when the sorted array has been rotated? Modified binary search.