Home›Study Resources›Computer Science›
How does a binary search work?
Computer Science
A-Level

How does a binary search work?

A binary search finds an item in a sorted list by repeatedly checking the middle item. If the middle item is the target, stop. If the target is smaller, discard the upper half; if larger, discard the lower half. Repeat until the item is found or no items remain. Its time complexity is O(log n). Example: Find 23 in [3, 8, 15, 23, 42, 57, 61]. Middle (index 3) = 23 Answer: Found at index 3 in one comparison.

Binary search is a divide-and-conquer algorithm that only works on sorted data. Each comparison halves the search space, so a list of 1 000 items needs at most about 10 comparisons. At A Level, compare it with linear search, trace it with low, high and mid pointers, and state its O(log n) complexity.

Worked example

Use a binary search to find 57 in [3, 8, 15, 23, 42, 57, 61] (indices 0 to 6).

  1. low = 0, high = 6, mid = (0 + 6) ÷ 2 = 3. Item 23 < 57, so set low = 4.
  2. low = 4, high = 6, mid = (4 + 6) ÷ 2 = 5. Item 57 = target.
  3. Stop: the item has been found.
  4. Comparisons made: 2.

Answer: 57 is found at index 5 after 2 comparisons.

Reviewed by

Want one-to-one support?

One-to-one online tuition can help you build confidence in your subject. Find a tutor who teaches your course.

Find a Tutor

Learn face to face in Glasgow

Prefer in-person lessons? Visit the ExpertTutor Glasgow Southside centre.

See the centre