Searching Algorithms

Searching algorithms locate a target value within a data structure. AQA 7517 requires knowledge of linear search and binary search.

Linear (Sequential) Search

Examines each element one by one from the start until the target is found or the end is reached.

FUNCTION linearSearch(arr, target)
  FOR i ← 0 TO len(arr) - 1
    IF arr[i] = target THEN
      RETURN i      // Found at index i
    END IF
  END FOR
  RETURN -1         // Not found
END FUNCTION

Linear Search Analysis

• Best case: O(1) — target is first element
• Worst case: O(n) — target is last or not present
• Average case: O(n)
• Prerequisite: None — works on unsorted data

Binary Search

Repeatedly halves the search space by comparing the target with the middle element. Requires the array to be sorted.

FUNCTION binarySearch(arr, target)
  left ← 0
  right ← len(arr) - 1
  WHILE left ≤ right
    mid ← (left + right) DIV 2
    IF arr[mid] = target THEN
      RETURN mid
    ELSE IF arr[mid] < target THEN
      left ← mid + 1    // Target in right half
    ELSE
      right ← mid - 1   // Target in left half
    END IF
  END WHILE
  RETURN -1             // Not found
END FUNCTION

Binary Search Trace

// Array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
// Target: 23
// Indices: 0  1  2   3   4   5   6   7   8   9

Step 1: left=0, right=9, mid=4, arr[4]=16 < 23 → left=5
Step 2: left=5, right=9, mid=7, arr[7]=56 > 23 → right=6
Step 3: left=5, right=6, mid=5, arr[5]=23 = 23 → FOUND at index 5 ✓

Binary Search Analysis

• Best case: O(1) — target is middle element
• Worst case: O(log n) — search space halved each time
• Prerequisite: Array must be sorted

Comparison