Standard searching algorithms: linear search and binary search, how each works step by step, the requirement that binary search needs a sorted list, and the comparison of their efficiency.

What this dot point is asking

OCR wants you to describe the two standard searching algorithms, linear search and binary search, step by step, to know that binary search needs a sorted list, and to compare their efficiency. You must be able to trace each on a given list and say which is appropriate for a situation. This is examined in Paper 2, often as a description or a comparison.

Linear search

In OCR Exam Reference Language, a linear search of a list data for a target:

found = false
i = 0
while i < data.length AND found == false
  if data[i] == target then
    found = true
    position = i
  endif
  i = i + 1
endwhile

Binary search

Comparing efficiency

The key comparison is how the work grows as the list gets bigger. Linear search checks items one by one, so doubling the list size roughly doubles the work in the worst case. Binary search halves the remaining items each step, so doubling the list size adds only one extra step. On a list of a million items, linear search may make up to a million comparisons, while binary search makes about twenty. The trade-off is that binary search needs the list to be sorted first, which takes time, so for a small list, an unsorted list, or a one-off search, linear search can be the better choice.

Try this

Q1. State one condition that must be true for a binary search to work. [1 mark]

• Cue. The list must be sorted (in order).

Q2. In the worst case, how many items does a linear search check in a list of 50 items? [1 mark]

• Cue. 50 (it may have to check every item).

Q3. Explain why binary search is faster than linear search on a large sorted list. [2 marks]

• Cue. Binary search discards half the remaining items at each step, so the number of items left shrinks very quickly, whereas linear search checks items one at a time.