Imagine hunting for a name in a phone book. You could read every entry from A to Z — that is linear search. Or open to the middle, decide which half holds the name, and discard the other — that is binary search. Both strategies work; one is dramatically faster on large datasets.

What is linear search and how does it work?

Linear search checks each item in a list one by one, from the beginning, until it finds the target or reaches the end. It makes no assumption about whether the list is sorted.

Pseudocode:

FUNCTION linearSearch(list, target)
    FOR i ← 0 TO len(list) - 1
        IF list[i] = target THEN
            RETURN i       // found at position i
        END IF
    END FOR
    RETURN -1              // not found
END FUNCTION

Trace example — searching for 7 in [4, 2, 7, 9, 1]:

Step Index checked Value Match?
1 0 4 No
2 1 2 No
3 2 7 Yes — return 2

What is binary search and how does it work?

Binary search requires a sorted list. It works by repeatedly halving the search space:

  1. Find the middle element.
  2. If it equals the target, you are done.
  3. If the target is smaller, repeat on the left half.
  4. If the target is larger, repeat on the right half.
  5. If the left and right pointers cross, the target is not in the list.

Pseudocode:

FUNCTION binarySearch(list, target)
    low  ← 0
    high ← len(list) - 1
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

Trace example — searching for 14 in [2, 5, 8, 12, 14, 23, 38] (seven elements, indices 0–6):

Pass low high mid list[mid] Decision
1 0 6 3 12 14 > 12 → low = 4
2 4 6 5 23 14 < 23 → high = 4
3 4 4 4 14 Found at index 4

Only three comparisons to find the target in seven items. For a list of one million sorted items, binary search needs at most 20 comparisons.

How do linear search and binary search compare?

Property Linear search Binary search
Works on unsorted data? Yes No — must be sorted first
Worst-case comparisons (n items) n log₂ n
Best case 1 (first item is the target) 1 (first midpoint is the target)
Simple to implement? Very simple More complex
Good for small lists? Yes Overkill
Good for large sorted lists? Slow Very fast

log₂ n means "how many times you can halve n before reaching 1." For 1,000 items: log₂ 1000 ≈ 10 comparisons maximum.

What does "worst case" mean for each algorithm?

For linear search, the worst case is when the target is the very last element or is not present at all — the algorithm inspects every element.

For binary search, the worst case is also when the target is absent, but even then the number of comparisons is only log₂ n. The trade-off is that you must pre-sort the data; if the list changes frequently, re-sorting may cost more time than linear search saves.

How would you write binary search in Python?

def binary_search(lst, target):
    low  = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid          # found: return index
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1                   # not found

numbers = [2, 5, 8, 12, 14, 23, 38]
print(binary_search(numbers, 14))   # 4
print(binary_search(numbers, 10))   # -1

Frequently asked questions

Yes — this is an absolute requirement. Binary search works by discarding half the remaining data at each step, which only makes sense if the data is in order. Applying binary search to an unsorted list produces wrong answers without any error message.

What happens in binary search if there are duplicate values?

Standard binary search will find one occurrence but not necessarily the first or the last. For GCSE purposes, assume all values are unique unless told otherwise.

Which algorithm should I use in my GCSE programming project?

If your data is already sorted and will not change frequently, binary search is the better choice for speed. If the data is unsorted or changes regularly, linear search is simpler and avoids the overhead of maintaining sorted order.

How do I remember which is which in the exam?

Think of the names: linear = straight line, check one after another. Binary = two halves, split and discard. The word "binary" is your reminder that the algorithm always divides into two.

Need to practise tracing search algorithms for your mock or controlled assessment? Visit aitutors.me — Professor Turing provides step-by-step guided traces at exam pace.