Binary Search — Sorting and Searching Algorithms | IGCSE Computer Science

Exam Frequency Analysis

Past paper frequency (2018 to 2024)

This topic accounts for approximately 7% of your exam marks.

stable

Low

Stable7%

Bubble sort traces and binary search descriptions appear in nearly every paper. 4 to 6 marks.

A binary search repeatedly halves the search range in a sorted list by comparing the middle element to the target.

Binary search is much faster than linear search on large lists, but it only works on a sorted list. If your data is not sorted, you must either sort it first or use a linear search.

Step-by-step algorithm

Step	What it does
1	Set `Low` to the index of the first element and `High` to the index of the last
2	Calculate the middle index: `Mid = (Low + High) DIV 2`
3	Compare the value at `Mid` with the target
4	If equal, the target is found; stop
5	If the target is less than the middle value, the target must be in the lower half: set `High = Mid − 1`
6	If the target is greater than the middle value, the target must be in the upper half: set `Low = Mid + 1`
7	Repeat steps 2-6 until the target is found, or until `Low > High` (search range empty, target not in list)

Each iteration halves the remaining search range. After k iterations, only n / 2^k items remain. This is why binary search is so fast.

Pseudocode

Low  ← 1
High ← LENGTH(Data)
Found ← FALSE

WHILE Low <= High AND Found = FALSE DO
   Mid ← (Low + High) DIV 2
   IF Data[Mid] = Target THEN
      Found ← TRUE
      OUTPUT "Target found at position ", Mid
   ELSE
      IF Target < Data[Mid] THEN
         High ← Mid - 1
      ELSE
         Low ← Mid + 1
      ENDIF
   ENDIF
ENDWHILE

IF Found = FALSE THEN
   OUTPUT "Target not found"
ENDIF

Example — Search the sorted list [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] for the value 13 using a binary search.

The list has 10 elements, with indices 1 to 10.

Step	Low	High	Mid	Data[Mid]	Comparison	Action
1	1	10	5	9	13 > 9	Search upper half: Low = 6
2	6	10	8	15	13 < 15	Search lower half: High = 7
3	6	7	6	11	13 > 11	Search upper half: Low = 7
4	7	7	7	13	13 = 13	Found at index 7

The search took 4 comparisons. A linear search on the same list would have taken 7 comparisons.

What if the target is not present?

If the target is not in the list, the search continues until Low > High. At that point, the range to search has shrunk to zero items, so the algorithm reports not found.

Example — Search the same list for 8. The algorithm narrows the range repeatedly, but never finds an exact match; eventually Low > High and it stops with "not found".

Advantages and disadvantages

Advantages	Disadvantages
Very fast on large lists: log₂(n) comparisons	Only works on sorted lists
Scales well: doubling the list adds just one more comparison	Slightly more complex to write than linear search
	If the list is unsorted, the cost of sorting first can exceed the saving

How long can a binary search take?

For a list of n items:

Best case: target is the middle element; only 1 comparison.
Worst case (or not present): about log₂(n) comparisons.

Size of list	Linear search (worst)	Binary search (worst)
10	10	4
100	100	7
1 000	1 000	10
1 000 000	1 000 000	20
1 000 000 000	1 000 000 000	30

Doubling the list adds only one more comparison to a binary search. Linear search has no such advantage.