Knowledge organisersSearching and sorting algorithms

Standard searching algorithms: Binary search

Knowledge organiser

Searching and sorting algorithms

2.1.3a

Understand the main steps of each algorithm, Understand any pre-requisites of an algorithm, Apply the algorithm to a data set, Identify an algorithm if given the code or pseudocode for it

What you need to know

Binary search is an efficient searching algorithm that works only on sorted lists. It repeatedly divides the list in half by comparing the middle element to the target value, then discarding the half that cannot contain the target. This divide-and-conquer approach makes it much faster than linear search for large datasets.

Key points

Pre-requisite:Binary search can ONLY be used on a SORTED list — the data must be in order.
Step 1: Find the MIDDLE item and compare it to the target.
THREE POSSIBILITIES: (1) Middle equals target → item found, stop. (2) Target is LESS than middle → discard right half, search left. (3) Target is GREATER than middle → discard left half, search right.
Repeat until the target is found or the remaining list is size 1 (or 0) and the item does not match.
Exam Tip:Many students forget to mention the case where the middle value EQUALS the target — always include all three possibilities.
Exam Tip:Binary search determines an item is NOT in the list when the remaining list is size 1/0 and not matched — NOT 'end of list' (that's linear search).
For even-length lists, pick either middle-left or middle-right consistently.
Advantage over linear search: more efficient / fewer comparisons needed, especially with large lists.
More complex to implement than linear search.

Code examples

Binary search in Python

python

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

numbers = [4, 7, 8, 11, 15, 18, 20]
print(binary_search(numbers, 8))  # Output: 2

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 data[mid] < target: low = mid + 1 else: high = mid - 1 return -1 # Not found numbers = [4, 7, 8, 11, 15, 18, 20] print(binary_search(numbers, 8)) # Output: 2