A-level Computer Science revision · Data structures and algorithms

Linear and binary search

The idea

Linear search checks each item in turn: it works on unsorted data and is O(n). Binary search compares the target with the middle item of a sorted list and discards half each time: O(log n). For n items, binary search needs at most about log₂n + 1 comparisons.

  1. Linear: check each item from the start.
  2. Binary: find midpoint, compare, discard half, repeat.
  3. Binary search requires sorted data.

Watch out Binary search does not work on unsorted data.

See it worked

Worked example

Binary search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72]. What is the first midpoint?

  1. 9 items, indices 0 to 8.
  2. Midpoint index (0 + 8) DIV 2 = 4.
  3. Value 16; 23 > 16 so search the right half.

Answer 16 (index 4)

Your turn

Question 12 marks

What is the maximum number of comparisons binary search needs to search a sorted list of 1000 items?

Question 21 mark

Which search can be used on an unsorted list?

Choose one
Question 31 mark

What is the worst-case time complexity of linear search?

Choose one

A-level Computer Science Pro, OCR H446

A-level Computer Science Pro

£119 once

Price rises to £199 on 1 January. Save £80 by joining before then.

At least 12 months of access

By paying you agree to our Terms and get access straight away, which ends your 14-day cancellation right.

No VAT is charged.

Independent practice for OCR A-level Computer Science (H446), not endorsed by OCR.

Privacy · Terms