How does binary search work and what are its pitfalls?
Interviewer Expectations for this Question
01
Core Competency
Assesses fundamental understanding of Data Structures & Algorithms conventions, runtime behavior, and memory/performance considerations.
02
Evaluation Criteria
Hiring managers look for precision, avoidance of ambiguous jargon, and ability to explain trade-offs under real production conditions.
Comprehensive Model Answer
Verified Solution
Binary search finds a target in a sorted array by halving the search range each step, giving O(log n).
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids overflow
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Pitfalls: off-by-one in the boundary update, using the wrong loop condition, integer overflow with (lo + hi) / 2, and forgetting the array must be sorted. Variants find the first/last occurrence using lower-bound and upper-bound templates.
Candidate Response Strategy & Interview Tips
- Start with a concise one-sentence summary: Deliver a direct, confident answer first before expanding into nuances.
- Demonstrate real-world trade-offs: Discuss where this approach excels and when you would avoid it in production systems.
- Discuss complexity & edge cases: Proactively explain time/space complexity or boundary conditions (null values, scale limits).
- Prepare for interviewer follow-ups: Technical hiring panels frequently probe deeper into concurrency, backward compatibility, or alternative libraries.