Binary Search
Search sorted data in logarithmic time.
What is Binary Search?
Binary search discards half of the remaining range after each comparison.
Important points
- Test empty, single-element, duplicate, and already sorted inputs.
- Separate correctness from optimization.
- Use the standard library in production unless a custom implementation is justified.
Binary Search visualizer
O(log n)Use Play or Step to follow each comparison and data movement.
C and C++ code examples
main.c
#include <stdio.h>
int search(const int *values, int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int middle = low + (high - low) / 2;
if (values[middle] == target) return middle;
if (values[middle] < target) low = middle + 1;
else high = middle - 1;
}
return -1;
}
int main(void) {
int values[] = {3, 7, 11, 16, 23, 28};
printf("index=%d\n", search(values, 6, 23));
}
index=4C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{3, 7, 11, 16, 23, 28};
auto match = std::lower_bound(values.begin(), values.end(), 23);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=4C and C++ comparison
The input must be sorted. The manual C loop and std::lower_bound both run in O(log n) on random-access ranges.
C
Loops, pointers, lengths, and temporary buffers are written explicitly.
C++
Iterators and standard algorithms separate operations from container representation.
Practice exercises
Run both versions, then modify them to observe the different language guarantees.
- Trace each comparison on paper.
- Test duplicates and extreme values.
- Benchmark the custom implementation against the standard library.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
All challenges