Binary search

Standard searching algorithms: Binary search

2.1.3 Searching and sorting algorithms

Searching and sorting algorithms — Note 1 of 5

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.

What to know

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.
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.

Pre-requisite

Binary search can ONLY be used on a SORTED list — the data must be in order.

Exam technique

Tip:Many students forget to mention the case where the middle value EQUALS the target — always include all three possibilities.
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).

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

Ready to test yourself?

Practise 2.1.3 questions

← Previous topicTrace tables2.1.2 Designing, creating and refining algorithms Next note →Linear search2.1.3 Searching and sorting algorithms

Back to Searching and sorting algorithms

Revise another OCR GCSE topic: Designing, creating and refining algorithms

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