Binary Search
Efficiently find an element in a sorted array by repeatedly dividing the search interval in half.
Find Target:
Ready to search
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.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).
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.