Show understanding of linear and binary searching methods

19.1 Algorithms – Searching Methods

Searching is the process of locating a target value within a collection of data. Two fundamental searching techniques are covered at A‑Level:

• Linear (sequential) search
• Binary (divide‑and‑conquer) search

1. Linear Search

Linear search examines each element of a list in order until the target is found or the end of the list is reached.

Pseudocode

function linearSearch(list, target):
for i from 0 to length(list)‑1 do
if list[i] = target then
return i          // index of target
return -1                 // not found

Key characteristics:

• Works on unsorted data.
• Best‑case time: \$O(1)\$ (target is the first element).
• Worst‑case and average time: \$O(n)\$, where \$n\$ is the number of elements.
• Space complexity: \$O(1)\$ (in‑place).

Step‑by‑step example

Find the value 23 in the list \$L = [5, 12, 23, 7, 19]\$.

1. Compare 5 with 23 → not equal.
2. Compare 12 with 23 → not equal.
3. Compare 23 with 23 → equal → return index 2.

2. Binary Search

Binary search repeatedly halves a sorted list, discarding the half that cannot contain the target.

Pseudocode

function binarySearch(sortedList, target):
low  = 0
high = length(sortedList)‑1
while low ≤ high do
mid = floor((low + high) / 2)
if sortedList[mid] = target then
return mid
else if sortedList[mid] < target then
low = mid + 1
else
high = mid – 1
return -1

Key characteristics:

• Requires the list to be sorted in non‑decreasing order.
• Best‑case time: \$O(1)\$ (target is the middle element).
• Worst‑case time: \$O(\log_2 n)\$.
• Space complexity: \$O(1)\$ for the iterative version; \$O(\log n)\$ for a recursive version due to call stack.

Step‑by‑step example

Find the value 23 in the sorted list \$S = [5, 7, 12, 19, 23, 31, 42]\$.

1. low = 0, high = 6 → mid = 3 → \$S[3]=19\$ < 23 → set low = 4.
2. low = 4, high = 6 → mid = 5 → \$S[5]=31\$ > 23 → set high = 4.
3. low = 4, high = 4 → mid = 4 → \$S[4]=23\$ → return index 4.

3. Comparison of Linear and Binary Search

4. Practical Considerations for A‑Level Exams

• Always state whether the list is sorted before choosing binary search.
• When writing pseudocode, include initialisation of indices and the loop condition clearly.
• Explain why binary search has logarithmic complexity: each iteration reduces the search interval to half its previous size, leading to the recurrence \$T(n)=T(n/2)+c\$, which solves to \$T(n)=O(\log n)\$.
• For linear search, emphasise that the algorithm is simple but inefficient for large \$n\$.
• Remember edge cases:

  • Empty list – both algorithms should return “not found”.
  • Target not present – linear search scans all elements; binary search exhausts the interval.
  • Duplicate values – linear search returns the first occurrence; binary search may return any occurrence unless modified.

5. Sample Exam Question

Question: Given the sorted array \$A = [3, 8, 15, 22, 27, 31, 44]\$, trace the execution of binary search to locate the value \$22\$. Show the values of low, high, and mid at each step and state the final index returned.

Answer (outline):

1. Initial: low = 0, high = 6 → mid = 3 → \$A[3]=22\$ → target found → return 3.

Because the target is the middle element, binary search finds it in a single iteration, demonstrating its \$O(1)\$ best‑case behaviour.