Review: Standard Binary Search
You'll learn: How binary search efficiently finds elements in sorted arrays by repeatedly halving the search space.
The Core Idea
Binary search is the go-to algorithm when you need to find a target value in a sorted array. Instead of checking every element one by one (linear search), binary search exploits the sorted order to eliminate half of the remaining possibilities with each comparison.
Think of it like guessing a number between 1 and 100. If someone says "higher" or "lower," you wouldn't guess randomly—you'd pick the middle and narrow down from there. That's binary search.
How It Works
- Start by examining the middle element of your search range
- If it matches your target, you're done!
- If the middle element is larger than your target, search the left half
- If the middle element is smaller than your target, search the right half
- Repeat until you find the target or run out of elements
The O(log n) Complexity Foundation
Binary search's power comes from halving the problem size each step. With 1,000 elements, you need at most 10 comparisons (since 2¹⁰ = 1,024). With 1,000,000 elements? Only about 20 comparisons. This logarithmic relationship—where doubling the input only adds one more step—makes binary search incredibly efficient for large datasets.
Critical Requirement
Binary search only works on sorted data. The algorithm's logic assumes elements are ordered. On unsorted data, binary search produces incorrect results.
Key Takeaway: Binary search achieves O(log n) search time by repeatedly dividing a sorted array in half, making it vastly superior to linear search for large datasets—but it requires the data to be sorted first.