Implement and trace linear search and binary search, state their complexities, and justify when each applies

What this dot point is asking

SEAB wants you to implement and trace linear search and binary search, state their time complexities, and justify when each is appropriate. The central idea is that exploiting structure pays off: a linear search makes no assumptions and is $O(n)$, but if the data is sorted, binary search discards half the possibilities each step and runs in $O(\log n)$.

The answer

Linear search

Linear search checks each element in turn until it finds the target or runs out:

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

It works on any list, sorted or not. In the worst case (target last or absent) it makes $n$ comparisons, so it is $O(n)$. Best case is $O(1)$ if the target is first.

Binary search

Binary search needs a sorted list. It compares the target with the middle element and discards the half that cannot contain it:

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]:
            low = mid + 1
        else:
            high = mid - 1
    return -1   # not found

Each step halves the range, so it needs at most $\log_2 n$ comparisons: $O(\log n)$.

Why the precondition matters

Binary search decides which half to keep based on order. On unsorted data that decision is invalid, so it can skip past the target and report "not found" incorrectly. The list must be sorted first; if it is not, either sort it (costing $O(n \log n)$) or use linear search.

Choosing between them

• Use linear search for small or unsorted lists, or when the list changes constantly so keeping it sorted is not worth it.
• Use binary search when the list is sorted (or stays sorted) and is large enough that $O(\log n)$ clearly beats $O(n)$.

Examples in context

Example 1. A phone contact list. Looking up a contact in an alphabetically sorted list is binary search: open the middle, decide earlier or later, repeat. Finding one name among ten thousand takes about 14 comparisons, which is why sorted indexes feel instant.

Example 2. Searching a log file as it is written. A live log appended to constantly is not kept sorted by content, so finding an error message means a linear scan. Here $O(n)$ is accepted because maintaining sort order on every append would cost more than the occasional search saves.

Try this

Q1. State the worst-case complexity of linear search and explain when it occurs. [2 marks]

• Cue. $O(n)$ - when the target is the last element or is absent, so all $n$ items are compared.

Q2. Why must a list be sorted for binary search to work? [2 marks]

• Cue. Binary search discards a half based on whether the target is greater or less than the middle value; without order, that decision is invalid and the target can be missed.

Q3. Roughly how many comparisons does binary search need for a sorted list of 1024 items in the worst case? [1 mark]

• Cue. About $\log_2 1024 = 10$ comparisons, since $2^{10} = 1024$.