Linear and binary search

The essentials

Linear (sequential) search compares the key with each element from the first onwards until it is found or the list ends. It works on sorted and unsorted lists. Binary search works only on a sorted list. It compares the key with the middle element; if they match, the search ends; if the key is smaller, the search continues in the left half; if larger, in the right half. Each step halves the part of the list still to be searched.

Key points

• Linear search, list of n elements: best case 1 comparison (key is first); worst case n comparisons (key is last or absent); on average about n/2 comparisons for a successful search.
• Binary search steps: low = 0, high = n − 1; repeat while low ≤ high: mid = (low + high) // 2; if list[mid] == key, found; if list[mid] < key, low = mid + 1; else high = mid − 1. If low > high, the key is absent.
• Binary search, list of n elements: best case 1 comparison (key at the first middle); worst case about ⌊log₂ n⌋ + 1 comparisons. For 1,000 elements this is at most 10 comparisons, compared with up to 1,000 for linear search.
• Dry run: in [5, 12, 18, 25, 31, 40, 47], searching for 40: mid = 3 (25 < 40) → low = 4; mid = 5 (40) found in 2 comparisons.
• Binary search is much faster on large lists, but the list must be kept sorted; linear search is simple and suits small or unsorted lists.

Exam tips

• Write low, high and mid for each step in a small table in your rough work.
• Doubling the list size adds only about one comparison to the worst case of binary search but doubles it for linear search.

Common mistakes

• Applying binary search to an unsorted list.
• Forgetting the floor division when calculating mid.