Searching Algorithms

This lesson covers linear search and binary search — the two fundamental searching algorithms in the OCR A-Level Computer Science (H446) specification. Understanding when and why to use each is essential.

---

What is Searching?

Searching is the process of finding a specific item (the target or key) within a collection of data. The two main approaches are:

Algorithm	Description	Requirement
Linear search	Check each item one by one	Works on any data (sorted or unsorted)
Binary search	Repeatedly halve the search space	Requires sorted data

---

Linear Search

Linear search (also called sequential search) checks each element in the collection one at a time, from the first to the last, until the target is found or the end is reached.

Pseudocode (OCR Style)

function linearSearch(data, target, size)
    for i = 0 to size - 1
        if data[i] == target then
            return i
        endif
    next i
    return -1
endfunction

Python Implementation

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i
    return -1

# Example
numbers = [7, 2, 9, 4, 6, 1, 8, 3, 5]
result = linear_search(numbers, 6)
print(result)    # Output: 4 (index of 6)

Worked Example: Trace Table

Search for 6 in [7, 2, 9, 4, 6, 1, 8, 3, 5]:

Step	i	data[i]	data[i] == 6?	Action
1	0	7	No	Continue
2	1	2	No	Continue
3	2	9	No	Continue
4	3	4	No	Continue
5	4	6	Yes	Return 4

Result: Found at index 4 (5 comparisons)

Time Complexity

Case	Comparisons	Complexity
Best case	1 (target is 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
Simple to implement	Slow for large data sets — O(n)
Works on unsorted data	Checks every element in the worst case
Works on any data structure	Not suitable when performance is critical

---

Binary Search

Binary search works by repeatedly dividing the search space in half. At each step, it compares the target with the middle element. If the target is smaller, search the left half; if larger, search the right half.

Prerequisite: Data Must Be Sorted

Binary search only works on sorted data. If the data is unsorted, you must sort it first (which has its own cost).

Pseudocode (OCR Style) — Iterative

function binarySearch(data, target, size)
    low = 0
    high = size - 1
    while low <= high
        mid = (low + high) DIV 2
        if data[mid] == target then
            return mid
        elseif target < data[mid] then
            high = mid - 1
        else
            low = mid + 1
        endif
    endwhile
    return -1
endfunction

Python Implementation

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# Example
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(numbers, 13)
print(result)    # Output: 6 (index of 13)

Worked Example: Trace Table