Searching Algorithms

Linear search

Check each item one at a time from the start until the target is found (or the list ends).

FOR each item in list
    IF item = target THEN return its position
return "not found"

• Works on any list, sorted or not.
• Worst case checks every item → slow on large lists.

Binary search

Repeatedly check the middle of a sorted list, discarding half each time.

1. Find the middle item
2. If it = target → found
3. If target < middle → search the LEFT half
4. If target > middle → search the RIGHT half
5. Repeat until found or no items left

Comparison

	Linear	Binary
List must be sorted?	No	Yes
Speed (large list)	Slow	Fast
1000 items, worst case	1000 checks	~10 checks

Binary search halves the list each step, so 1000 items take at most ~10 checks (because 2¹⁰ ≈ 1000).

Exam tip

If the list is sorted and large, binary search is the expected answer. Binary search cannot be used on an unsorted list.