All subjects · Mathematics · WDM11 (D1)

Binary search

Binary search finds an item in an **ordered** list by checking the middle item and throwing away half the list each time.

Method

1. Number the items 1 to N. 2. The middle item is in position (first + last)/2, rounded up. 3. If it is the target, stop. If the target comes before it, keep the items before it; otherwise keep the items after it. The middle item is discarded too. 4. Repeat on the remaining list. If the list becomes empty, the item is not there.

What to write

Show each middle position as a calculation, for example (1 + 13)/2 = 7, the item there, and the sub-list you keep. Finish with a clear sentence: 'Karim found in position 11' or 'Bilal is not in the list'.

How many checks

Each check at least halves the list. For N items the greatest number of checks is the smallest n with 2n > N. For example, 13 items need at most 4 checks, since 24 = 16 > 13.

Worked example

Use binary search to look for Karim in: Ahmed, Bella, Chen, Dina, Ezra, Farah, Gita, Hana, Isla, Jamal, Karim, Lena, Musa.

  1. Middle position 7: Gita
  2. Middle position 11: Karim (found)

Answer: Karim is found in position 11

Key idea: List must be ordered; middle = (first + last)/2 rounded up; discard the middle item and the half that cannot contain the target.

Check yourself

  1. A binary search is applied to the 13 names Ahmed, Bella, Chen, Dina, Ezra, Farah, Gita, Hana, Isla, Jamal, Karim, Lena, Musa. In which position is the first middle item?
    Show answer

    7. (1 + 13)/2 = 7.

  2. Binary search for 31 in 3, 8, 12, 15, 19, 23, 27, 31, 36, 40, 44. How many items are checked before 31 is found (including the check that finds it)?
    Show answer

    3. Middle items: position 6 (23); position 9 (36); position 8 (31).

  3. Binary search for 20 in 3, 8, 12, 15, 19, 23, 27, 31, 36, 40, 44. The first middle item is 23 in position 6. Which item is checked next?
    • 12
    • 19
    • 15
    • 27
    Show answer

    12. 20 < 23, so keep positions 1 to 5. Middle (1 + 5)/2 = 3, which is 12.

  4. What is the correct conclusion of a binary search for Bilal in Ahmed, Bella, Chen, Dina, Ezra, Farah, Gita, Hana, Isla, Jamal, Karim, Lena, Musa?
    • Bilal is in position 2
    • Bilal is in position 1
    • The search cannot be done on names
    • Bilal is not in the list
    Show answer

    Bilal is not in the list. Middle items checked: Gita (position 7); Dina (position 4); Bella (position 2); Chen (position 3). The list then becomes empty, so Bilal is not there.

  5. What is the maximum number of items a binary search checks in an ordered list of 100 items?
    Show answer

    7. 26 = 64 is not more than 100, but 27 = 128 is, so at most 7 checks.

  6. Why can binary search not be used directly on an unsorted list?
    • Unsorted lists are too long
    • It only works on numbers
    • The middle item cannot be found
    • Discarding half the list relies on the items being in order
    Show answer

    Discarding half the list relies on the items being in order. Only in an ordered list do you know the target must be on one particular side of the middle item.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.