RavnaryA Knowledge Platform
Colour theme

Card 01/ 09

Take the quiz

ConceptDifficulty: Intermediate3 min

Binary Search: Halving a Sorted Range

Compare with the middle, keep the half that can still hold the target, and repeat.

Binary search finds a value in a sorted array by comparing it with the middle item and discarding the half that cannot hold it, so every comparison halves what is left to check. This card covers how one search runs, what it costs, and the signs that a problem wants it. You meet it wherever sorted data is searched many times: an index of sorted keys, a list of timestamps, a price list.

The search keeps two indices, low and high, that bound the part of the array still in play, starting at the first and last index. Each step computes mid, the index halfway between them rounded down, and compares the item there with the target. If they are equal, the search is over. If the middle item is smaller, the target can only be to its right, so low moves to mid + 1. If it is larger, high moves to mid - 1. When low passes high, nothing is left to check and the target is not there. The trace below searches for 44 in eight sorted numbers; watch the three markers close in.

Binary search for 44 in eight sorted numbers

Input4 9 15 21 28 37 44 52, indices 0 to 7

  1. Compare 44 with 21

    1. 4low
    2. 9
    3. 15
    4. 21mid
    5. 28
    6. 37
    7. 44
    8. 52high

    21 is smaller than 44, so 44 can only be to the right of index 3: low moves to 4.

  2. Compare 44 with 37

    1. 4
    2. 9
    3. 15
    4. 21
    5. 28low
    6. 37mid
    7. 44
    8. 52high

    37 is smaller than 44, so 44 can only be to the right of index 5: low moves to 6.

  3. Compare 44 with 44

    1. 4
    2. 9
    3. 15
    4. 21
    5. 28
    6. 37
    7. 44lowmid
    8. 52high

    44 equals the target, so the search returns index 6 after three comparisons.

ResultFound at index 6

Three comparisons settled a search of eight items. Each one at least halves the range, so n items need at most about log2 n + 1 comparisons: 20 for a million, where a scan from the front may read all million. A printed dictionary is searched the same way, opened in the middle and kept on whichever side the word falls. The likeness breaks in where you open it: a person jumps near the right letter by feel, and binary search always takes the exact middle, which is what makes its cost guaranteed.

The sort order is what licenses throwing a half away. On an unsorted array a small middle item says nothing about where the target lies, and the search can report a value missing when it is there. The costs, for an array of n items, are these.

Binary search on a sorted array of n items
Best case
O(1)
the first middle item is the target
Average case
O(log n)
over every target in the array
Worst case
O(log n)
the target is absent or found last
Extra space
O(1)
the loop; a recursive version uses O(log n) stack
Input
Sorted
by the order the comparisons use

The cues are sorted input, many lookups, and a question phrased as "find the position of" or "where would this go".

Binary search

Use it when

  • The data is sorted, or is searched often enough to repay sorting it once
  • Any item can be read by its index in constant time, as in an array
  • The question is where a value is, or where it would go

Avoid it when

  • The data is unsorted and searched once: a scan costs O(n), less than an O(n log n) sort
  • The data is in a linked list, where reaching the middle costs O(n)
  • Only exact-key lookups matter and order never does: a hash table answers in O(1) on average

Keeping data sorted costs something on every insert, and binary search is the return on that cost: a lookup whose price grows with the number of digits in n rather than with n itself.

← → move through sections and cards