Linear Search (OCR A-Level Computer Science): Revision Notes

Linear Search

Overview

Linear Search is a simple algorithm used to find the position of a target value in a list. It works by sequentially checking each element of the list until the target is found or the end of the list is reached. Linear Search is easy to implement but can be inefficient for large datasets.

How Linear Search Works

• Process:
  1. Start at the first element of the list.
  2. Compare each element with the target value.
  3. If a match is found, return the position of the element.
  4. If the end of the list is reached without finding the target, return an indication that the target is not in the list.
• Applicable to:
  • Both unsorted and sorted datasets.

Time Complexity

• Best Case: O(1) (target is the first element).
• Worst Case: O(n) (target is the last element or not present).
• Average Case: O(n/2), simplified to O(n).

Space Complexity

• O(1), as no extra memory is required beyond the input list.

Pseudocode for Linear Search

METHOD LinearSearch(array, target)
    FOR i FROM 0 TO array.length - 1
        IF array[i] = target
            RETURN i  // Target found at index i
    ENDFOR
    RETURN -1  // Target not found

Python Example

def linear_search(array, target):
    for i in range(len(array)):
        if array[i] == target:
            return i  # Target found
    return -1  # Target not found

# Example usage:
data = [3, 7, 10, 15, 18, 20]
print(linear_search(data, 15))  # Output: 3
print(linear_search(data, 5))   # Output: -1

Tracing Linear Search

Note Summary