Maintain a window [lo, hi] over the sorted array, initially the whole array. Compute the midpoint, compare the middle element to the key: if equal, you're done; if the key is larger, the answer can only be in the upper half, so set lo = mid + 1; if smaller, set hi = mid - 1. Each comparison discards half the remaining elements, so you converge in at most ⌈log₂ n⌉ steps, O(log n) time, O(1) space iteratively (O(log n) stack if recursive). The precondition is that the data is sorted; that's what lets you discard half based on one comparison. The intuition for why it's so fast: doubling the array size adds only one extra comparison, so even a million elements take ~20 steps. The loop ends when lo > hi, meaning the window is empty and the key is absent.
Data Structures & Algorithms · Interview question
Walk through how binary search works and its complexity.
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Linear & Binary Search
O(n) linear scan works on anything; O(log n) binary search needs sorted data and gives deterministic worst-case timing, plus the overflow and off-by-one bugs that haunt it.