Searching Algorithms

A searching algorithm finds whether a target value exists in a list, and if so, at which position. OCR J277 requires knowledge of two searching algorithms:

Algorithm	Pre-requisite	Best for
Linear search	None — works on any list	Short or unsorted lists
Binary search	List must be sorted first	Long sorted lists

OCR J277 does not require you to write or memorise code for these algorithms. You must be able to apply them step by step to a given data set, and identify them if shown pseudocode or a description.

Choosing the right algorithm matters in practice: searching a database of 1,000,000 records with linear search could require 1,000,000 comparisons. Binary search reduces this to at most 20 comparisons (since $\lceil {\log }_{2}1,000,000\rceil =20$).

A linear search works through a list one element at a time, from the first item to the last, comparing each element to the target.

Steps:

1. Start at index 0.
2. Compare the current element to the target.
3. If they match, return the current index — the item is found.
4. If they do not match, move to the next index.
5. If the end of the list is reached without a match, return "not found".

(Extra context — OCR J277 does not require you to write or recall pseudocode for linear search; understanding the steps and applying them to a data set is what is assessed.)

PROCEDURE linearSearch(list, target)
    FOR i = 0 TO len(list) - 1
        IF list[i] == target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1
END PROCEDURE

Linear search works on any list — sorted or unsorted. Its simplicity is its main advantage.

(Extra context — time complexity is not required by OCR J277: in the worst case, linear search performs $n$ comparisons for a list of $n$ items.)

Search for 9 in the list: [4, 7, 2, 9, 1, 5]

Step	Index	Value checked	Match?
1	0	4	No
2	1	7	No
3	2	2	No
4	3	9	Yes — found at index 3

The search stops as soon as the match is found. In this case, 4 comparisons were needed.

Search for 6 in the same list: [4, 7, 2, 9, 1, 5]

Step	Index	Value checked	Match?
1	0	4	No
2	1	7	No
3	2	2	No
4	3	9	No
5	4	1	No
6	5	5	No
—	—	End of list	Not found

All 6 elements are checked before returning "not found". This is the worst case for a 6-element list.

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

Pre-requisite: the list must be sorted (ascending or descending) before binary search can be applied. If the list is unsorted, binary search gives incorrect results.

Steps:

1. Set low = 0, high = last index.
2. Calculate mid = (low + high) DIV 2 (integer division — round down).
3. Compare list[mid] to the target.
   • If equal: item found at mid.
   • If target < list[mid]: target must be in the lower half — set high = mid - 1.
   • If target > list[mid]: target must be in the upper half — set low = mid + 1.
4. Repeat from step 2 until found, or until low > high (not found).

Binary search halves the remaining search space with each comparison. A sorted list of 1,024 items requires at most 10 comparisons; 1,048,576 items require at most 20.

Search for 23 in the sorted list: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9)

Pass	low	high	mid	list[mid]	Action
1	0	9	4	16	23 > 16 → set low = 5
2	5	9	7	56	23 < 56 → set high = 6
3	5	6	5	23	23 == 23 → found at index 5

Only 3 comparisons needed to find 23 in a 10-element list.

Search for 10 in the same list:

Pass	low	high	mid	list[mid]	Action
1	0	9	4	16	10 < 16 → set high = 3
2	0	3	1	5	10 > 5 → set low = 2
3	2	3	2	8	10 > 8 → set low = 3
4	3	3	3	12	10 < 12 → set high = 2
—	3	2	—	—	low > high → not found

When low > high, the search space is empty — the target does not exist in the list.

Feature	Linear search	Binary search
Pre-requisite	None	List must be sorted
Works on unsorted list?	Yes	No
Maximum comparisons (n items)	$n$	$\lceil {\log }_{2}n\rceil$
Best case	1 comparison (first element)	1 comparison (target is mid)
Worst case	$n$ comparisons	$\lceil {\log }_{2}n\rceil$ comparisons
Suitable for small lists?	Yes	Yes, but sorting overhead may negate benefit
Suitable for large sorted lists?	Inefficient	Much more efficient

Example: searching a list of 1,024 sorted items:

• Linear search: up to 1,024 comparisons
• Binary search: up to 10 comparisons ($\lceil {\log }_{2}1,024\rceil =10$)

Use binary search when the list is already sorted and large. Use linear search for unsorted data or very small lists where the overhead of sorting is not worthwhile.

1. Applying binary search to an unsorted list

Binary search only works correctly on a sorted list. If the list is not sorted and you apply binary search, you will get the wrong answer. The pre-requisite is frequently tested — always check whether the list is sorted before choosing binary search.

2. Calculating the midpoint incorrectly

Use integer division: mid = (low + high) DIV 2. For low = 5, high = 9: mid = 14 DIV 2 = 7, not 7.5. Always round down.

3. Not updating low/high correctly after the comparison

• Target > list[mid] → low = mid + 1 (not low = mid)
• Target < list[mid] → high = mid - 1 (not high = mid)

Failing to add/subtract 1 can cause an infinite loop.

4. Stopping the trace before checking the "not found" condition

A binary search ends when found or when low > high. Show the final row where low > high to confirm the target is absent — don't just stop at the last comparison.

Mistake	Correction
Using binary search on [7, 2, 9, 1]	Sort to [1, 2, 7, 9] first, or use linear search
mid = (5 + 9) / 2 = 7.5	mid = (5 + 9) DIV 2 = 7
Setting low = mid after "target > list[mid]"	Set low = mid + 1