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.

Binary search repeatedly halves the search space by comparing the target to the middle element of the current range.

Requirement: the list must be sorted in ascending order before binary search is applied. The algorithm assumes that if the target is less than the midpoint, it cannot be in the right half — this assumption is only valid on sorted data.

Logic at each step:

1. Calculate the midpoint: mid = (low + high) ÷ 2 (round down if not whole)
2. If list[mid] = target → found; return mid
3. If target < list[mid] → target is in the left half; set high = mid − 1
4. If target > list[mid] → target is in the right half; set low = mid + 1
5. If low > high → target is not in the list

Each step eliminates half the remaining elements. The number of comparisons needed grows with ${\log }_2(n)$: doubling the list size adds only one extra comparison.

Find the value 14 in the sorted list [2, 5, 8, 11, 14, 19, 23, 30] (indices 0–7):

Step	low	high	mid	list[mid]	Decision
1	0	7	3	11	14 > 11 → search right half
2	4	7	5	19	14 < 19 → search left half
3	4	4	4	14	Match — found at index 4

Result: found at index 4, in 3 comparisons.

Find the value 6 (not present) in the same list:

Step	low	high	mid	list[mid]	Decision
1	0	7	3	11	6 < 11 → search left half
2	0	2	1	5	6 > 5 → search right half
3	2	2	2	8	6 < 8 → search left half
4	2	1	—	—	low > high → Not found

Feature	Linear search	Binary search
Sorted list required	No	Yes
Best case	1 comparison	1 comparison
Worst case	$n$ comparisons	$\approx {\log }_2(n)$ comparisons
Worst case for 1,000 items	1,000	≤ 10
Worst case for 1,000,000 items	1,000,000	≤ 20

Use linear search when:

• The list is unsorted (or too small to justify sorting first)
• The list changes frequently, making sorting expensive to maintain
• Simplicity of implementation matters

Use binary search when:

• The list is already sorted and large
• Many repeated searches will be run on the same static dataset

Binary search is dramatically faster on large datasets, but the sorting requirement is a genuine cost. If a list must be sorted specifically to enable binary search, the total cost of (sort + search) may exceed a simple linear search on small or frequently-updated data.

1. Applying binary search to an unsorted list

Binary search produces incorrect results on unsorted data. The algorithm assumes elements outside the search range can be discarded — this is only valid when the list is sorted. Always state or check that sorting is required.

2. Rounding the midpoint up instead of down

mid = (low + high) ÷ 2, rounded down (integer division). For low = 0, high = 7: mid = 3.5 → 3, not 4.

3. Setting low = mid or high = mid after a non-match

After eliminating the midpoint, set low = mid + 1 (right half) or high = mid − 1 (left half). Using mid instead of mid ± 1 means the midpoint is rechecked on the next step, which can cause an infinite loop.

4. Stopping a trace before confirming "not found"

When the target is absent, the algorithm must run until low > high — then output "not found." Students often stop at the last comparison without completing the termination check.

5. Claiming binary search is always the better choice

Binary search is faster per search, but it requires sorted data. On a small or frequently modified list, the overhead of sorting may make linear search the more practical option overall.