Writing a Binary Search in Pseudocode

Binary search is one of the most famous and commonly used algorithms in computer science. Used to find a specific value within a sorted array, it boasts a highly efficient time complexity of O(log n).

It achieves this incredible speed by utilizing a divide and conquer strategy. Instead of checking every single item one by one (like a Linear Search), it compares the target value to the middle element of the array. If it doesn't match, it completely eliminates half of the remaining search space and repeats the process.

While the concept is elegant, implementing binary search using pointers and loops can be challenging. In this guide, we will break down the algorithm into core logical steps before explicitly defining the syntax and rules for the AQA, OCR, and Cambridge (CIE) exam boards.

Core Concepts: The Divide and Conquer Approach

A binary search algorithm relies on three variables acting as "pointers": a left pointer, a right pointer, and a mid pointer. Let's look at how they work together.

The Pre-requisite: Sorting

The most critical rule of a binary search is that the array must already be sorted. If the data is random, you cannot safely eliminate half of the array because you don't know where smaller or larger numbers might be hiding.

Finding the Midpoint

Inside a loop, we calculate the middle index by adding the left and right pointers together and performing integer division (dropping any decimals). We then check if the item at this midpoint is our target.

Adjusting the Pointers

If the midpoint isn't our target, we adjust our boundaries. If the value at the midpoint is less than our target, we know the target must be in the right half, so we move the left pointer to mid + 1. If it is greater, we move the right pointer to mid - 1.

Syntax Variations by Exam Board

Because pseudocode is not standardized globally, you must adapt your keywords and operators depending on the specification you are taking.

AQA Pseudocode Standard

AQA expects capitalized control structures and relies heavily on the DIV operator for integer division (which is critical to prevent decimals in your array index).

• Subroutines: SUBROUTINE BinarySearch(arr, target).
• Length: LEN(arr).
• Division: DIV 2.

OCR Pseudocode Standard

OCR syntax is Python-like, utilizing lowercase keywords. Integer division can be represented simply using DIV or standard double slashes // depending on preference.

• Subroutines: function binarySearch(arr, target).
• Operators: Uses standard = for assignment and == for equivalence.

Cambridge (CIE / 9618) Standard

CIE requires strict data typing. You must declare the integer types of your pointers, and specify the return type of the function itself. Note that CIE arrays often start at index 1 rather than 0.

• Function Setup: FUNCTION BinSearch(MyArray : ARRAY, Target : INTEGER) RETURNS INTEGER.
• Declarations: DECLARE Mid : INTEGER.

The Full Algorithm Example

Below is a complete, working example of a binary search structured cleanly in AQA-style pseudocode. Returning -1 at the very end acts as a flag to indicate the target was not found anywhere in the array.

Conclusion

Binary search is a beautiful introduction to algorithm optimization. By simply halving the dataset on every iteration, a search through one billion items takes a maximum of only 30 checks!

When writing this out in an exam, the most common mistakes are forgetting to use integer division for the midpoint (which breaks array indexing) and getting the < or > signs confused when adjusting the left and right pointers. Practice tracing this algorithm on paper to solidify your understanding.