Binary Search: Efficient Searching in Sorted Arrays
You'll learn how to search a sorted array much faster than linear search by repeatedly cutting the search area in half.
The Core Idea
Imagine looking up a word in a physical dictionary. You don't start at page 1 and flip through every page—you open somewhere in the middle, see if your word comes before or after that page, then eliminate half the dictionary and repeat. Binary search works exactly the same way.
Requirements: Your array must be sorted first. That's the trade-off for speed.
How It Works
- Start by looking at the middle element of the array
- Compare it to your target value
- If it matches, you're done!
- If the target is smaller, discard the right half and repeat on the left half
- If the target is larger, discard the left half and repeat on the right half
- Continue until you find the target or run out of elements
Why It's Fast
Each comparison eliminates half of the remaining elements. This means:
- 1,000 elements? Maximum 10 comparisons
- 1,000,000 elements? Maximum 20 comparisons
- Linear search would need up to 1,000,000 comparisons in the worst case!
This is called O(log n) time complexity—the time grows logarithmically with the array size, not linearly.
The Divide-and-Conquer Strategy
Binary search is your first encounter with divide-and-conquer: break a big problem into smaller pieces, solve the smaller piece, and ignore the rest. Each step divides the problem size by 2.
Key Takeaway: Binary search finds elements in sorted arrays in O(log n) time by repeatedly halving the search space, making it dramatically faster than linear search for large datasets.