Linear Search and Binary Search

A searching algorithm locates a specific value (the target) within a list and returns its position, or reports that it is absent. Searching is one of the most common operations in computing — looking up a contact, finding a record in a database, or checking whether a username already exists all require a search.

GCSE Computer Science requires two algorithms:

Algorithm	Sorted list required?	Worst-case comparisons
Linear search	No	$n$ (entire list)
Binary search	Yes	${\log }_2(n)$

For a list of 1,000 items: linear search may check all 1,000 elements; binary search needs at most 10 comparisons (since $2^{10}=1,024>1,000$).

A comparison is each time the algorithm checks whether an element matches the target. Fewer comparisons means a faster algorithm.

Linear search checks each element in the list in sequence, starting from the first, until the target is found or the end of the list is reached.

Algorithm in pseudocode:

found ← False
i ← 0
WHILE i < length(list) AND found = False
    IF list[i] = target THEN
        found ← True
        OUTPUT i
    END IF
    i ← i + 1
END WHILE
IF found = False THEN
    OUTPUT "Not found"
END IF

Key properties:

• Works on unsorted and sorted lists — no preprocessing required
• Best case: target is the first element → 1 comparison
• Worst case: target is the last element, or absent → $n$ comparisons
• Average case: approximately $n/2$ comparisons

Linear search's simplicity is its strength: it requires no prior sorting and works on any list, regardless of order or data type.

Find the value 7 in the list [3, 9, 1, 7, 5, 2]:

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

Result: found at index 3, in 4 comparisons.

Find the value 8 (not present) in [3, 9, 1, 7, 5, 2]:

Step	Index checked	Value	Match?
1	0	3	No
2	1	9	No
3	2	1	No
4	3	7	No
5	4	5	No
6	5	2	No

Result: not found, 6 comparisons — the worst case for a 6-element list.