LESSON 4 · PATTERN GUIDE

Binary Search on Sorted Data

Discard half the remaining sorted search space after each comparison.

FIRST, LEARN THE PATTERNMaintain a range that could still contain the answer. Compare the midpoint and update one boundary while preserving the range invariant.

Input is sorted, or a condition changes monotonically from false to true or true to false.

How to approach it

Use mid = left + floor((right - left) / 2). Decide carefully whether the active interval is closed or half-open, and return the boundary the invariant describes.

Watch out for

Duplicates and boundary answers require explicit handling; a basic exact-match search may not find the first or last occurrence.

A CLOSER EXPLANATION

Binary search works because sorted order lets one comparison rule out an entire half of the candidates. Keep an invariant such as 'the answer is still inside [left, right]' and update boundaries so it remains true. This reduces O(n) scanning to O(log n) comparisons.

NOW YOU TRY

Practice question

In [2, 4, 4, 4, 7, 9], find the first index containing 4.

EXAMPLEsorted = [2, 4, 4, 4, 7, 9], target = 4Give your answer before revealing the explanation.

Show a hint

Store the match as a candidate, then move the right boundary leftward.

Show an answer

Index 1 (zero-based). Continue searching left after finding a match.

CONNECT IT TO REAL LIFE

Binary Search on Sorted Data at work

A library catalog lists book IDs in sorted order. There are 1,024 entries. About how many midpoint checks are needed to find one ID, or establish it is absent?

Show one possible approach

At most about 11 checks, since each check halves the remaining entries and 2¹⁰ = 1,024 (with one final boundary check depending on the implementation).

Practice next

Use these problem IDs to find additional practice for this pattern:

333435153162704