Searching: Linear and Binary

Why Searching Matters

Searching is one of the most fundamental operations in computing. Every time you look up a contact on your phone, query a database, or ask a search engine a question, a search algorithm is running in the background. Your exam covers two searching algorithms: linear search and binary search. Understanding when to use each one, and being able to trace them by hand, are core exam skills.

Linear Search

Linear search (also called sequential search) is the simplest possible search algorithm. It checks each item in the list from the first to the last, one at a time, until it either finds the target or runs out of items. It works on any list — sorted or unsorted.

Below is a linear search in pseudocode. It searches a list called names for the value stored in target:

SET found = FALSE
SET i = 0
WHILE i < LENGTH(names) AND found = FALSE
  IF names[i] = target THEN
    SET found = TRUE
    OUTPUT “Found at position ” & i
  END IF
  SET i = i + 1
END WHILE
IF found = FALSE THEN
  OUTPUT “Not found”
END IF

Binary Search

Binary search is much faster than linear search on large lists, but it has one critical requirement: the list must be sorted before binary search can be applied. Binary search works by repeatedly halving the search space. It finds the middle item, compares it to the target, and discards the half of the list that cannot contain the target.

Here is the binary search algorithm in pseudocode:

SET low = 0
SET high = LENGTH(list) - 1
SET found = FALSE
WHILE low <= high AND found = FALSE
  SET mid = (low + high) DIV 2
  IF list[mid] = target THEN
    OUTPUT “Found at position ” & mid
    SET found = TRUE
  ELSE IF target < list[mid] THEN
    SET high = mid - 1
  ELSE
    SET low = mid + 1
  END IF
END WHILE
IF found = FALSE THEN
  OUTPUT “Not found”
END IF

Comparing Linear and Binary Search

The table below summarises the key differences. In exam “compare” questions, you must make explicit contrasts — say “unlike linear search…” rather than describing each in a separate paragraph.

Feature	Linear search	Binary search
List must be sorted?	No	Yes
Worst-case comparisons (n items)	n	log₂n
Best-case comparisons	1 (target is first)	1 (target is midpoint)
Works on small lists?	Yes — often simpler	Yes, but overhead of sorting may not be worth it
Works on large lists?	Slow — may check millions of items	Fast — 30 comparisons suffices for 1 billion items

Choosing Between Linear and Binary Search

The right algorithm depends entirely on two questions: is the list already sorted, and how often will you search it? If the data arrives in arbitrary order and only needs to be searched once, the cost of sorting first is wasted, so a linear search wins. If the same dataset is searched repeatedly, the one-off sorting cost is paid back many times over because every subsequent binary search runs in logarithmic time. Long-lived data structures — phone books, dictionaries, sorted database indexes — are designed around this trade-off.

Binary search also assumes you can jump straight to any position in the data. An array lets you do that, because you can read any index directly. If a question asks why binary search is unsuitable in a scenario, the reason is almost always that the data is not sorted.