SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-binary-search-needs-sorted

What must be true about a list before you can use binary search on it?

It must be sorted, or the halving trick gives wrong answers.

Start playing free

  1. It must have no repeated values
  2. It must be sorted ✔
  3. It must have a power-of-two length

Why: Binary search decides which half to keep by comparing with the middle item. That only works if smaller items are all on one side and bigger items on the other, which is what sorted means.

Huh, didn't know that: Sorting once and then searching many times is a classic trade: pay O(n log n) up front, then each search is O(log n).

The dad joke
My binary search failed on my messy bookshelf. Turns out it was a sort of problem.
Like this card?
Play the game

References

Answer: It must be sorted. Binary search decides which half to keep by comparing with the middle item. That only works if smaller items are all on one side and bigger items on the other, which is what sorted means.

  1. MIT 6.006 Introduction to Algorithms, Lecture 3: Sorting ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec3
    Given a sorted array, we can leverage binary search to make an efficient set data structure.
    Checked 2026-10-10.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsWhat does it mean that a sorting algorithm is stable?Tech & GadgetsHow fast is binary search on a sorted array of n items, in Big O terms?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?

That's stuff everyone should know.