Foundations · Unit 7

Binary Search

Think about finding a word in a paper dictionary. You do not start on page one and read every word. You flip to the middle, see whether your word comes before or after, and throw away half the dictionary in a single move. Then you do it again with what is left. A few flips and you are there, even in a book with a hundred thousand words.

That is binary search. Each step cuts the remaining possibilities in half, so the work grows painfully slowly: doubling the size of the data adds just one more step. A linear scan of a million items can take a million checks. Binary search takes about twenty.

But there is a catch that is easy to forget and fatal to ignore: the dictionary trick only works because the words are in order. Binary search lives or dies on sorted input. This unit covers why that is, how the halving gives you O(log n), and the boundary mistakes that quietly break it.

Goal: Explain why binary search needs sorted input, how halving gives O(log n), and the off-by-one traps that break it.

Lesson 1 of 50%

You’re not signed in. Your progress here won’t be saved.

The one requirement: sorted input

Binary search works by looking at the middle element and deciding which half to keep. That decision only makes sense if the data is sorted. In a sorted array, if the middle value is too small, everything to its left is also too small, so you can throw the whole left half away. That single comparison rules out half the data.

In an unsorted array, the middle tells you nothing about the rest. The value you want could be anywhere, on either side, so you cannot rule out a single element. No order, no halving, no binary search. This is the first thing to check before you reach for it.

Why does binary search require the array to be sorted?

Premium practice

The drills and graded test are premium

The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:

✓2 applied drills: train spotting when the concept applies
✓A 5-question graded test to clear the unit
✓The full guided problem ladder with faded hints, plus the cold-read capstone

Unlock everything →

From $6/month. Cancel anytime.