If the data is sorted, halve the search space each step. O(log n). Know three variants for arrays — and know how to extend the same idea to search over the answer space itself.
What Is It?
Binary search repeatedly divides a sorted search space in half. You maintain two pointers l and r bounding the possible range, compute the midpoint m, and compare. Based on the comparison, you eliminate half the range. After log₂(n) steps, you've found your answer (or determined it doesn't exist).
There are three core variants for searching arrays:
Exact match: Find the index of a specific target. Returns -1 if not found.