Searching Algorithms: Linear Search and Binary Search

What is linear search and how does it work?

Linear search checks each item in a list one by one, from the beginning, until it finds the target or reaches the end. It makes no assumption about whether the list is sorted.

Pseudocode:

FUNCTION linearSearch(list, target)
    FOR i ← 0 TO len(list) - 1
        IF list[i] = target THEN
            RETURN i       // found at position i
        END IF
    END FOR
    RETURN -1              // not found
END FUNCTION

Trace example — searching for 7 in [4, 2, 7, 9, 1]:

What is binary search and how does it work?

Binary search requires a sorted list. It works by repeatedly halving the search space:

1. Find the middle element.
2. If it equals the target, you are done.
3. If the target is smaller, repeat on the left half.
4. If the target is larger, repeat on the right half.
5. If the left and right pointers cross, the target is not in the list.

Pseudocode:

FUNCTION binarySearch(list, target)
    low  ← 0
    high ← len(list) - 1
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSE IF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        END IF
    END WHILE
    RETURN -1
END FUNCTION

How do you trace through a binary search?

Trace example — searching for 14 in [2, 5, 8, 12, 14, 23, 38] (seven elements, indices 0–6):

Only three comparisons to find the target in seven items. For a list of one million sorted items, binary search needs at most 20 comparisons.

How do linear search and binary search compare?

log₂ n means "how many times you can halve n before reaching 1." For 1,000 items: log₂ 1000 ≈ 10 comparisons maximum.

What does "worst case" mean for each algorithm?

For linear search, the worst case is when the target is the very last element or is not present at all — the algorithm inspects every element.

For binary search, the worst case is also when the target is absent, but even then the number of comparisons is only log₂ n. The trade-off is that you must pre-sort the data; if the list changes frequently, re-sorting may cost more time than linear search saves.

How would you write binary search in Python?

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

numbers = [2, 5, 8, 12, 14, 23, 38]
print(binary_search(numbers, 14))   # 4
print(binary_search(numbers, 10))   # -1

Frequently asked questions

Does the list have to be sorted before binary search?

Yes — this is an absolute requirement. Binary search works by discarding half the remaining data at each step, which only makes sense if the data is in order. Applying binary search to an unsorted list produces wrong answers without any error message.

What happens in binary search if there are duplicate values?

Standard binary search will find one occurrence but not necessarily the first or the last. For GCSE purposes, assume all values are unique unless told otherwise.

Which algorithm should I use in my GCSE programming project?

If your data is already sorted and will not change frequently, binary search is the better choice for speed. If the data is unsorted or changes regularly, linear search is simpler and avoids the overhead of maintaining sorted order.

How do I remember which is which in the exam?

Think of the names: linear = straight line, check one after another. Binary = two halves, split and discard. The word "binary" is your reminder that the algorithm always divides into two.

---

For Socratic KS3 tutoring and free GCSE flashcards, see aitutors.me.