What is Binary Search?
Learn what binary search is, how it halves the search space for O(log n) lookups on sorted data, with Python code and interview practice.
Expected Interview Answer
Binary search is an algorithm that finds a target value in a sorted collection by repeatedly halving the search range, comparing the target to the middle element, giving O(log n) time.
It starts with the full range and checks the middle element: if it matches the target, the search is done; if the target is smaller, the search continues on the left half; if larger, it continues on the right half. Each comparison discards half the remaining candidates, so a million-item array needs only about twenty comparisons. The algorithm requires the data to already be sorted, and it can be written iteratively or recursively, with the iterative form avoiding call-stack overhead.
- O(log n) time on sorted data
- Predictable, low comparison count
- Simple iterative implementation
- Basis for many search-space-reduction algorithms
AI Mentor Explanation
Finding a specific over’s score in a printed, page-numbered scorecard means opening to the middle page first, not page one. If the over you want happened earlier, you flip to the middle of the first half; if later, the middle of the second half. Each flip eliminates half the remaining pages, so even a 500-page tournament record narrows down in under ten flips. That halving, not scanning page by page, is what binary search does.
Step-by-Step Explanation
Step 1
Confirm the data is sorted
Binary search only works correctly on sorted input.
Step 2
Set low and high bounds
Start with the full index range of the array.
Step 3
Compare against the middle
Compute mid and compare arr[mid] to the target.
Step 4
Halve the range and repeat
Move low or high past mid depending on the comparison until found or the range is empty.
What Interviewer Expects
- Explanation that the input must be sorted
- Correct O(log n) time complexity reasoning
- Correct handling of the mid-index and off-by-one bounds
- Ability to write it iteratively without bugs
Common Mistakes
- Running binary search on unsorted data
- Off-by-one errors in updating low/high bounds
- Infinite loops from not moving mid correctly
- Integer overflow when computing mid as (lo+hi)/2 in some languages
Best Answer (HR Friendly)
“Binary search is a fast way to find something in a sorted list by repeatedly checking the middle item and eliminating half the remaining possibilities each time, so it finds an answer in a handful of steps even in huge datasets.”
Code Example
def binary_search(sorted_items, target):
lo, hi = 0, len(sorted_items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sorted_items[mid] == target:
return mid
if sorted_items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Follow-up Questions
- How would you find the first occurrence of a duplicate value with binary search?
- How does binary search apply to rotated sorted arrays?
- What is the difference between binary search on values versus on the answer space?
- Why does binary search require random access, ruling out plain linked lists?
MCQ Practice
1. What is the time complexity of binary search on a sorted array of n elements?
Each comparison halves the search space, giving logarithmic time.
2. What precondition does binary search require on its input?
Binary search relies on ordering to safely discard half the range each step.
3. How many comparisons does binary search need in the worst case for 1,000,000 elements?
log2(1,000,000) is approximately 20, matching binary search’s worst case.
Flash Cards
Binary search precondition? — The collection must already be sorted.
Binary search time complexity? — O(log n) because each step halves the search space.
Mid comparison result? — Match returns the index; otherwise search continues in the half that could contain the target.
Common bug? — Off-by-one errors when updating low/high bounds.