Binary Search
On a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Guess-my-number from 1 to 100: you say 50; “higher”; 75; “lower”; 62… Every guess cuts the possibilities in half. You’ll always win within 7 guesses. That’s binary search.
The algorithm (array must be sorted)
low = 0,high = n - 1.- While
low <= high:mid = (low + high) / 2- if
a[mid] == key→ found. - if
a[mid] < key→ the key can only be on the right:low = mid + 1. - else → it can only be on the left:
high = mid - 1.
- If the loop ends, the key isn’t there: return −1.
Why O(log n)
After each comparison the range halves: n → n/2 → n/4 → … → 1. The number of halvings is log₂ n. For a million items that’s about 20 comparisons instead of a million.
Two requirements
- Sorted data, otherwise discarding a half is wrong.
- Random access (an array), so jumping to
midis O(1). On a linked list, reaching the middle costs O(n), which ruins the speed.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Search 38, then a missing value like 40. Count the comparisons.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
using namespace std;
int binarySearch(const int a[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // same as (low+high)/2, but cannot overflow
if (a[mid] == key) return mid;
else if (a[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main() {
int a[] = {3, 8, 12, 17, 23, 31, 38, 45, 52, 60}; // must be sorted
int n = 10;
cout << "search 38 -> " << binarySearch(a, n, 38) << "\n";
cout << "search 3 -> " << binarySearch(a, n, 3) << "\n";
cout << "search 40 -> " << binarySearch(a, n, 40) << "\n";
}search 38 -> 6 search 3 -> 0 search 40 -> -1
05Complexity
| Best case | O(1): key is at the first mid |
|---|---|
| Average / worst case | O(log n): about ⌊log₂ n⌋ + 1 comparisons |
| 1,000,000 items | at most 20 comparisons |
| Needs sorted data? | Yes, and random access (an array, not a linked list) |
| Extra space | O(1) iterative · O(log n) recursive (call stack) |
06Watch
What is binary search
Why this one: Builds the idea from scratch and writes careful code including the edge cases.
Binary search in 4 minutes
Why this one: Four-minute visual summary.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- Trace binary search for key 23 in
2, 5, 8, 12, 16, 23, 38, 56, 72, 91, giving low, mid and high at each step. - Write an iterative binary search function in C++.
- What is the worst-case number of comparisons for n = 1024?
- Why can't binary search be applied to a linked list efficiently?
Common mistakes
- Using
while (low < high)instead oflow <= high. That misses a key when one item is left. - Setting
low = midorhigh = midinstead ofmid ± 1, which can loop forever. - Running it on unsorted data. The result is meaningless.
(low + high) / 2can overflow for huge arrays;low + (high - low) / 2is safe.
08Quick check
09Practice
🟢 Trace by hand
Trace binary search for 23 and for 50 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 (indices 0–9).
Show answer
Key 23: (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 ✓ 3 comparisons
Key 50: (0,9) mid 4 = 16 → low 5 · (5,9) mid 7 = 56 → high 6 · (5,6) mid 5 = 23 → low 6 · (6,6) mid 6 = 38 → low 7 · low > high → −1 after 4 comparisons
🟡 Implement it
Write firstOccurrence(a, n, key) that returns the first index of key in a sorted array with duplicates.
Hint
When a[mid] == key, don't return. Record ans = mid and keep searching left with high = mid - 1.
Solution
int firstOccurrence(const int a[], int n, int key) {
int low = 0, high = n - 1, ans = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (a[mid] == key) { ans = mid; high = mid - 1; }
else if (a[mid] < key) low = mid + 1;
else high = mid - 1;
}
return ans;
}🔴 Solve problems
Hint
The textbook version. Get it right without looking.
Hint
When the loop ends without finding the key,
lowis exactly where it would be inserted.Hint
Binary search on the answer. Same pattern as firstOccurrence.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.