What is Binary Search?
Binary Search is an algorithm that finds a specific value in a sorted array. By halving the search range at each step, it locates any value among n elements in at most log₂(n) comparisons.
Think of looking up a word in a dictionary — you don't start from page one. You open the middle, decide if the word comes before or after, and repeat. That's exactly how binary search works.
Why Does It Matter?
Binary search is one of the most frequently tested algorithms in coding interviews.
- •Time complexity: O(log n) — searches 1 million elements in at most 20 steps
- •Applications: Array lookup, parametric search, Lower/Upper Bound
- •Interview favorite: Appears in Google, Meta, Amazon, and virtually every tech interview
How It Works
Step 1. Calculate the middle index (mid) of the array.
Step 2. Compare the middle element with the target value:
- •target == arr[mid] → Found it
- •target < arr[mid] → Search the left half
- •target > arr[mid] → Search the right half
Step 3. Repeat until the range is empty.
Time and Space Complexity
| Complexity | |
|---|---|
| Time (Best) | O(1) |
| Time (Average/Worst) | O(log n) |
| Space (Iterative) | O(1) |
| Space (Recursive) | O(log n) |
Since the search range halves each time, the complexity is O(log n). Even 1 billion elements need only about 30 comparisons.
The Key Requirement
The array must be sorted. Binary search cannot work on unsorted data. If sorting is needed, sort first in O(n log n), then apply binary search.
Common Variations in Interviews
Lower Bound — Find the first position where the value is ≥ target. Useful when duplicates exist.
Upper Bound — Find the first position where the value is > target.
Parametric Search — Use binary search to find the minimum/maximum value that satisfies a condition. Problems like "cutting trees" or "cutting cables" are classic examples.
Common Mistakes
- •Integer overflow in mid calculation: Use
left + (right - left) / 2instead of(left + right) / 2 - •Infinite loops: Incorrect updates to left/right boundaries prevent termination
- •Forgetting to sort: Always verify the array is sorted before applying binary search
See It in Action on AlgoNote
Watch binary search narrow down the range step by step on AlgoNote. Change the array size and target value to experiment and build real understanding.