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

The algorithm finds 42 at index 1 after 2 comparisons.

Complexity Analysis

Case	Comparisons	Big O
Best case	1 (target is the first element)	O(1)
Worst case	n (target is last or not present)	O(n)
Average case	n/2	O(n)

Advantages and Disadvantages

Advantages	Disadvantages
Works on unsorted data	Slow for large datasets
Simple to implement	Checks every element in the worst case
Works on any data structure (arrays, linked lists)	Not suitable when fast lookup is critical

---

Binary Search

How It Works

Binary search is a divide and conquer algorithm that works only on sorted data. It repeatedly divides the search space in half by comparing the target to the middle element.

Algorithm Steps

1. Set low = 0 and high = n - 1.
2. Calculate mid = (low + high) DIV 2.
3. If arr[mid] = target, return mid.
4. If target < arr[mid], set high = mid - 1 (search the left half).
5. If target > arr[mid], set low = mid + 1 (search the right half).
6. Repeat steps 2-5 until low > high (target not found).

Pseudocode

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

Trace Table Example

Searching for 35 in the sorted list [8, 17, 23, 35, 42, 56, 71, 89]: