Binary Search
Binary search finds an element in a sorted array by repeatedly dividing the search interval in half.
Intuition
You have probably used binary search in real life without even realizing it. For example, if you have ever looked up a word in a dictionary, you probably flipped to about the middle, checked the first letter, and then either checked the left or right half depending on the first letter of the word you were looking for. We repeat this process until we find the word.
Concept
Binary search is a search algorithm that runs in O(log n) in the worst case, where n is the size of the search space.
For binary search to work, your search space usually needs to be sorted. It is based on the idea of repeatedly dividing the search interval in half.
How it Works
Start by checking the element in the middle of the array. If this element is too small, then we know every element in the left half will also be too small (since the array is sorted). We can discard the left half. Similarly, if the element is too large, we discard the right half. We repeat this process of cutting the array in half until we find our target.
Step-by-Step Breakdown
- Start in the middle: Pick the item right in the center of your list.
- Compare: Is this the number you are looking for?
- Yes? You found it!
- Too Small? Ignore the entire left side. Your number must be on the right.
- Too Big? Ignore the entire right side. Your number must be on the left.
- Repeat: Now take the remaining part of the list and do the same thing. Keep cutting the list in half until you find your number!
When to Use
- Sorted Data: The fundamental requirement.
- Large Datasets: O(log n) is vastly faster than O(n) for large n (e.g. 1 billion items takes only ~30 ops).
- Random Access: Works best with Arrays/Vectors where accessing
midis O(1).
When NOT to Use
- Unsorted Data: Unless you sort it first (which takes O(n log n)).
- Linked Lists: Finding the middle element is O(n), negating the benefit.
- Small Datasets: Linear search might be faster due to CPU caching and branching overhead.
How to Identify
Look for keywords like "Sorted Array", "Monotonic Function", or constraints asking for O(log n) time complexity. Also applicable when finding a boundary (e.g., first bad version) or searching in a range (answer is between X and Y).
Preparing for interviews? This topic is also taught as a pattern:
Binary Search
Applying for software engineering roles? Free, no sign-up: