Binary Search Algorithm

This lesson covers the binary search algorithm as required by OCR J277 Section 2.2. Binary search is the second standard searching algorithm you must know for the OCR GCSE Computer Science exam. It is significantly more efficient than linear search, but it has an important requirement — the data must be sorted before binary search can be used.

---

What Is Binary Search?

Binary search is a searching algorithm that works by repeatedly dividing the search area in half. Instead of checking every element like linear search, binary search eliminates half of the remaining elements with each comparison.

Think of it like looking up a word in a dictionary — you open it near the middle, check whether your word comes before or after the current page, and then repeat on the relevant half.

---

How Binary Search Works

1. Find the middle element of the sorted list.
2. Compare the middle element with the target value.
3. If the middle element equals the target, the search is complete — return its position.
4. If the target is less than the middle element, discard the right half and repeat on the left half.
5. If the target is greater than the middle element, discard the left half and repeat on the right half.
6. Repeat until the target is found or the search area is empty (low > high).

The following flowchart shows the binary search decision process:

flowchart TD
    A([Start]) --> B["Set low = 0\nhigh = length - 1"]
    B --> C{"low <= high?"}
    C -- No --> D["Target not found\nReturn -1"]
    D --> Z([End])
    C -- Yes --> E["mid = low + high DIV 2"]
    E --> F{"list[mid]\n= target?"}
    F -- Yes --> G["Found! Return mid"]
    G --> Z
    F -- No --> H{"target <\nlist[mid]?"}
    H -- Yes --> I["high = mid - 1"]
    H -- No --> J["low = mid + 1"]
    I --> C
    J --> C

---

Binary Search in OCR Pseudocode

function binarySearch(list, target)
    low = 0
    high = list.length - 1

    while low <= high
        mid = (low + high) DIV 2
        if list[mid] == target then
            return mid
        elseif list[mid] < target then
            low = mid + 1
        else
            high = mid - 1
        endif
    endwhile

    return -1
endfunction

OCR Exam Tip: Note the use of DIV (integer division) to calculate the midpoint. This is an important OCR pseudocode convention — do not use / for integer division in pseudocode.

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
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# Example usage
numbers = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(numbers, 7)
print("Found at index:", result)  # Output: Found at index: 3

---

Tracing Through Binary Search

Let us trace through searching for 9 in the sorted list [1, 3, 5, 7, 9, 11, 13]:

Step	low	high	mid	list[mid]	Comparison	Action
1	0	6	3	7	9 > 7	Set low = 4
2	4	6	5	11	9 < 11	Set high = 4
3	4	4	4	9	9 == 9	Found! Return 4

The value 9 was found at index 4 after only 3 comparisons (out of 7 elements).

---

Properties of Binary Search

Property	Detail
Data requirement	Data must be sorted before searching
Best case	Target is the middle element — 1 comparison (O(1))
Worst case	O(log n) comparisons — much faster than linear search
How it works	Divides the search area in half each time
Complexity	More complex to implement than linear search

---

Understanding O(log n)

For a list of n items, binary search needs at most log₂(n) comparisons:

List Size (n)	Max Comparisons (log₂ n)
8	3
16	4
100	7
1,000	10
1,000,000	20

This is dramatically faster than linear search's O(n). For a million items, binary search needs at most 20 comparisons, while linear search might need up to 1,000,000.

---

When to Use Binary Search

Binary search is ideal when:

• The data is already sorted (or it is efficient to sort it first).
• The dataset is large — the efficiency gain over linear search is significant.
• You need to search the same data multiple times (sort once, search many times).

Binary search is not suitable when:

• The data is unsorted and sorting would be too costly.
• The list is very small — the overhead of binary search is not worth it.

---

Worked Exam-Style Example

Question: A sorted array contains [10, 20, 30, 40, 50, 60, 70, 80]. Use binary search to find the value 60. Show each step.

Answer:

Step 1: low=0, high=7, mid=3, list[3]=40. 60 > 40, so set low=4. Step 2: low=4, high=7, mid=5, list[5]=60. 60 == 60. Found at index 5.

---

Summary

• Binary search divides the search space in half each time.
• Data must be sorted for binary search to work.
• It is much faster than linear search: O(log n) vs O(n).
• You must be able to write it, trace it, and explain when it is appropriate.

OCR Exam Tip: A common mistake is forgetting to state that binary search requires sorted data. This is worth a mark in almost every binary search question. Always mention this requirement.

---

Extended Trace: Searching for a Value That Is Not Present

Let us trace searching for 6 in the sorted list [1, 3, 5, 7, 9, 11, 13] (note 6 is not in the list):

Step	low	high	mid	list[mid]	Comparison	Action
1	0	6	3	7	6 < 7	Set high = 2
2	0	2	1	3	6 > 3	Set low = 2
3	2	2	2	5	6 > 5	Set low = 3
4	3	2	—	—	low > high	Return -1

The loop terminates when low exceeds high, which is the algorithm's way of saying "the search space is empty". The function returns -1 to indicate the value is not present.

---

Extended Trace: A Larger Sorted List