Binary Search
Binary Search is a highly efficient algorithm for finding a target value within a sorted array. Instead of checking every element one by one (linear search), it repeatedly divides the search space in half, eliminating half the remaining elements with each comparison. This makes it dramatically faster for large datasets.
Learning Objectives
- 11.5.2.5 Write pseudocode for a binary search algorithm
Conceptual Anchor
The Dictionary Analogy
When looking up a word in a dictionary, you don't start from page 1. You open to the middle, check if your word comes before or after that page, then repeat with the correct half. Each time you halve the remaining pages. A 1000-page dictionary only needs about 10 steps to find any word. That's binary search.
Critical Prerequisite
Binary search only works on sorted data. If the array is unsorted, you must sort it first. This is the #1 fact examiners test — always state this in your answer.
Rules & Theory
How Binary Search Works
- Set low = 0 (first index) and high = n − 1 (last index)
- Calculate mid = (low + high) / 2 (integer division, round down)
- Compare
arr[mid]with the target:- ● If
arr[mid] = target→ Found! Return mid - ● If
arr[mid] < target→ target is in the right half →low = mid + 1 - ● If
arr[mid] > target→ target is in the left half →high = mid − 1
- ● If
- Repeat until
low > high→ target not found
| Property | Binary Search | Linear Search |
|---|---|---|
| Time Complexity (Best) | O(1) — target at middle | O(1) — target at start |
| Time Complexity (Worst) | O(log₂ n) | O(n) |
| Requires sorted data? | Yes | No |
| 1,000 elements worst case | ~10 comparisons | 1,000 comparisons |
| 1,000,000 elements worst case | ~20 comparisons | 1,000,000 comparisons |
Pseudocode:
FUNCTION BinarySearch(arr : ARRAY, n : INTEGER, target : INTEGER) RETURNS INTEGER
DECLARE low : INTEGER ← 0
DECLARE high : INTEGER ← n - 1
WHILE low <= high
DECLARE mid : INTEGER ← (low + high) DIV 2
IF arr[mid] = target THEN
RETURN mid // Found — return index
ELSE IF arr[mid] < target THEN
low ← mid + 1 // Search right half
ELSE
high ← mid - 1 // Search left half
ENDIF
ENDWHILE
RETURN -1 // Not found
ENDFUNCTIONC++:
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == target) {
return mid; // Found
} else if (arr[mid] < target) {
low = mid + 1; // Search right half
} else {
high = mid - 1; // Search left half
}
}
return -1; // Not found
}
int main() {
int data[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int n = 10;
int target = 23;
int result = binarySearch(data, n, target);
if (result != -1) {
cout << target << " found at index " << result << endl;
} else {
cout << target << " not found" << endl;
}
return 0;
}Worked Examples
T Trace — Binary Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
| Step | low | high | mid | arr[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23 → low = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23 → high = 6 |
| 3 | 5 | 6 | 5 | 23 | 23 = 23 → Found at index 5! |
Only 3 comparisons for a 10-element array. Linear search would have needed 6 comparisons.
T Trace — Binary Search for 15 (NOT in array) in [2, 5, 8, 12, 16, 23, 38]
| Step | low | high | mid | arr[mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 12 | 12 < 15 → low = 4 |
| 2 | 4 | 6 | 5 | 23 | 23 > 15 → high = 4 |
| 3 | 4 | 4 | 4 | 16 | 16 > 15 → high = 3 |
| 4 | 4 | 3 | — | — | low > high → Not found, return −1 |
Pitfalls & Common Errors
Forgetting to State "Array Must Be Sorted"
This is the most frequent exam mark lost. If asked to describe or explain binary search, always state: "The array must be sorted first." Examiners specifically look for this.
Using = Instead of <= in the While Condition
while (low <= high) is correct. Using while (low < high) will
miss the case where the target is the last remaining element (when low == high).
Integer Overflow in mid Calculation
For very large arrays, (low + high) can overflow. A safer formula is
mid = low + (high - low) / 2. Not required for exams, but good to know for
real-world code.
Off-by-One in low/high Updates
After comparing, set low = mid + 1 or high = mid − 1. NOT
low = mid or high = mid — this causes infinite loops because mid never
moves past the current element.
Pro-Tips for Exams
Maximum Comparisons Formula
The maximum number of comparisons for binary search on n elements is ⌊log₂ n⌋ + 1. For n=1000: ⌊log₂ 1000⌋ + 1 = 9 + 1 = 10. Learn this — it's a common exam question.
When to Use Which Search
- Data is sorted → Binary Search (O(log n))
- Data is unsorted → Linear Search (O(n)), OR sort first then binary search if searching multiple times
- Data is small (< 20 elements) → Linear search is simpler and fast enough
Graded Tasks
State two preconditions for using binary search. What is its time complexity?
Explain why binary search is O(log₂ n) using the concept of "halving the search space."
Trace binary search for the value 42 in [3, 7, 11, 19, 27, 35, 42, 50, 63]. Show low, high, mid, and arr[mid] at each step.
Write a C++ program that reads 10 sorted integers and a target from the user, performs binary search, and outputs either the index or "Not found."
An array has 1,000,000 elements. Compare the maximum number of comparisons needed by linear search vs binary search. Show your calculation.
Write pseudocode for a modified binary search that finds the first occurrence of a duplicate value (e.g., finding the first "23" in [5, 12, 23, 23, 23, 30]).