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