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

How fast is binary search on a sorted array of n items, in Big O terms?

O(log n), because every check throws away half of what is left.

Start playing free

  1. O(log n) ✔
  2. O(n)
  3. O(1)

Why: Binary search looks at the middle item, then keeps only the half that can still hold the answer. Halving again and again means about 20 checks for a million items, not a million.

Huh, didn't know that: Doubling the search range raises the logarithmic comparison bound by about one step.

The dad joke
I tried binary search on my sock drawer. Half my problems disappeared every time I looked.
Like this card?
Play the game

References

Answer: O(log n). Binary search looks at the middle item, then keeps only the half that can still hold the answer. Halving again and again means about 20 checks for a million items, not a million.

  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
    faster finds via binary search: O(log n)
    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 must be true about a list before you can use binary search on it?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?Tech & GadgetsWhat is the worst-case running time of insertion sort on n items?

That's stuff everyone should know.