Linear Search and Binary Search

Searching is one of the most fundamental operations in computing. Given a collection of data, we often need to determine whether a particular value exists and, if so, where it is located. At A-Level you must understand two key searching algorithms — linear search and binary search — and be able to compare their time complexity, trace their execution, and identify when each is appropriate.

---

Linear Search

How It Works

Linear search (also called sequential search) checks each element in the list one by one, starting from the first element, until the target is found or the end of the list is reached.

Pseudocode

FUNCTION linearSearch(arr, n, target)
    FOR i = 0 TO n - 1
        IF arr[i] = target THEN
            RETURN i
        END IF
    END FOR
    RETURN -1
END FUNCTION

Trace Table Example

Searching for 42 in the list [17, 42, 8, 35, 91]:

Step	i	arr[i]	arr[i] = 42?	Action
1	0	17	No	Continue
2	1	42	Yes	Return 1