What is Binary Search?
A binary search is a much more efficient searching algorithm than linear search. Instead of checking every element, it repeatedly halves the search area. Critical requirement: the list must be sorted in ascending order before binary search can be applied.
How Binary Search Works — Step by Step
- Find the middle element of the current search area (use integer division: (low + high) DIV 2)
- Compare the middle element with the target
- If they match → target found; return position
- If target < middle → search the left half (discard right half)
- If target > middle → search the right half (discard left half)
- Repeat until found or search area is empty (not found)
Binary Search — Example
List: [3, 7, 12, 18, 24, 35, 41, 56, 68, 79] — Search for 35
| Step | Low | High | Mid index | Mid value | Action |
|---|
| 1 | 0 | 9 | 4 | 24 | 35 > 24 → search right |
| 2 | 5 | 9 | 7 | 56 | 35 < 56 → search left |
| 3 | 5 | 6 | 5 | 35 | ✅ Found at index 5 |
Only 3 comparisons to find the target in a 10-item list!
Binary Search — Pseudocode (Edexcel 4CP0)
SET low TO 0
SET high TO LENGTH(list) - 1
SET found TO FALSE
WHILE low <= high AND found = FALSE DO
SET mid TO (low + high) DIV 2
IF list[mid] = target THEN
SET found TO TRUE
SEND "Found at " & mid TO DISPLAY
ELSE IF target < list[mid] THEN
SET high TO mid - 1
ELSE
SET low TO mid + 1
END IF
END WHILE
IF found = FALSE THEN
SEND "Not found" TO DISPLAY
END IF
Comparison: Binary vs Linear Search
| Feature | Linear Search | Binary Search |
|---|
| List must be sorted? | No | Yes |
| Best case | 1 comparison | 1 comparison |
| Worst case | n comparisons | log₂(n) comparisons |
| Efficiency for large lists | Slow | Fast |
| Complexity | O(n) | O(log n) |
📝 Exam Tip: You must be able to trace a binary search step by step, showing the low, high and mid values at each step. Remember: mid = (low + high) DIV 2 (integer division).
⚠️ Common Mistakes
- Applying binary search to an unsorted list — it only works on sorted lists
- Using mid = (low + high) / 2 — must use DIV (integer division) to get a whole index
- Forgetting to update low or high after each step — this causes an infinite loop