You are given nums, an array of integers sorted in ascending order, and an integer target.
Return the index of target if it exists in nums. If it does not, return -1.
The catch: your algorithm must run in O(log n) time. A plain left-to-right scan does not qualify — the array is sorted for a reason, and the whole game is to exploit that.
target against the middle element tell you about the rest of the array?nums[mid] < target, then every element at or before mid is also too small — the target cannot be in the left half. One comparison just eliminated half the candidates.lo and hi bounding the region that could still contain target. Loop while lo <= hi, probe mid = lo + (hi - lo) / 2, and shrink to the surviving half. Halving each step is exactly O(log n).O(log n) as part of the problem, not just a fast wall-clock time. At n = 10^4 a scan finishes quickly, but it does not demonstrate the required algorithm — and in an interview, scanning a sorted array signals you missed the point of the question.lo + hi can overflow when both are near the type's maximum. lo + (hi - lo) / 2 computes the same midpoint without ever forming the large sum. Python integers cannot overflow, but the habit is worth keeping everywhere.nums[mid] < target must imply everything left of mid is also smaller. Without sorting, you may throw away the half that actually contains the target and get -1 for a present element.lo <= hi, a one-element window (lo == hi) still gets probed — necessary, since that lone element might be the target. With lo < hi you would exit before checking it. The pairing rule: lo <= hi goes with mid + 1 / mid - 1 updates.-1, return lo after the loop — lo always lands on the first position with a value >= target. Same loop, different return.mid as a candidate and keep searching left (hi = mid - 1). The last recorded candidate is the leftmost occurrence, still in O(log n).[lo, hi] window is still properly sorted. Check which half is sorted, decide whether the target lies in it, and discard the other — binary search survives with one extra comparison per step.(lo + hi) / 2 overflow bug hid inside widely used standard-library implementations for roughly two decades before being noticed and fixed.git bisect binary-searches your commit history to find the commit that broke the build.Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 9 exists in nums and its index is 4.
Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 2 does not exist in nums, so we return -1.
- 1 <= nums.length <= 10^4 - -10^4 < nums[i], target < 10^4 - All the integers in nums are unique. - nums is sorted in ascending order.
Binary search is the most reused algorithm in all of interviewing — it hides inside dozens of harder problems (search in rotated arrays, finding boundaries, minimizing a feasible answer). Master the loop here, on the cleanest possible version, and you own the pattern forever.
n repeatedly reaches 1 in about log2(n) steps — that is why halving-based search is O(log n).target exists, it lives in nums[lo..hi].In plain English: keep a window [lo, hi] that could still contain target. Probe the middle. If the middle is the target, done. If the middle is too small, the target can only be to the right; if too big, only to the left. Shrink the window to that side and repeat until you find it or the window empties.
Formally: given a sorted array nums of distinct integers and an integer target, return the index i with nums[i] == target, or -1 if no such index exists, in O(log n) time.
Worked example — nums = [-1, 0, 3, 5, 9, 12], target = 9
idx: 0 1 2 3 4 5
[-1, 0, 3, 5, 9, 12]
lo mid hi nums[2] = 3 < 9 → search right
lo mid hi nums[4] = 9 → return 4 ✓
Two comparisons for six elements. A linear scan would have used five.
Asking two or three sharp questions before writing code is exactly what separates a senior interview from a junior one — it shows you design against guarantees, not assumptions.
“Is the array guaranteed to be sorted in ascending order?”
Everything hinges on this. Binary search on an unsorted array returns garbage silently — no crash, just wrong answers.
“Are all elements distinct?”
Yes here. With duplicates you would need to specify which index to return (first? any?), which changes the loop.
“Can the array have just one element?”
Yes — length can be 1. The loop must handle lo == hi correctly and probe that single element.
“What if target is smaller than every element or larger than every element?”
The window shrinks off the end, lo crosses hi, and we return -1. A correct implementation needs no special case for this.
“How large can the array be?”
Up to 10^4 elements. Small enough that a linear scan runs fast — but the problem explicitly demands O(log n), so the scan fails the requirement, not the clock.
Before I code, let me confirm the guarantees: the array is sorted ascending and all values are distinct, correct?
Since it is sorted and you want O of log n, this is a textbook binary search — I will keep a lo and hi window and halve it each step.
I will make sure the empty-window case falls out naturally and returns minus one, including when the target is off either end.
If nums[mid] < target, then every element at or left of mid is also < target — none of them can be the answer. One comparison, and mid + 1 elements vanish. This is the entire superpower of sorted data.
[-1, 0, 3, | 5, 9, 12] target = 9, nums[mid] = 3 ✗ ✗ ✗ ← all provably too small, discard without looking
The window size goes n → n/2 → n/4 → … → 1. That chain has about log2(n) links. For n = 10^4, that is at most 14 probes. Doubling the array adds one probe — this is why binary search scales almost for free.
Maintain: if target exists, its index is in [lo, hi]. Both updates preserve it (lo = mid + 1 and hi = mid - 1 only discard proven-impossible territory), and the loop runs while lo <= hi — a non-empty window. When lo > hi, the invariant says the target cannot exist anywhere: return -1. Every off-by-one bug in binary search is a violation of this invariant.
| Linear scan | Binary search | |
|---|---|---|
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Probes for n = 10^4 | up to 10,000 | at most 14 |
| Uses the sorted property | yes — that is the whole trick |
Full code for both approaches is in the Approaches selector below.
Key takeaway
When data is sorted, never scan — probe the middle and discard half per comparison. The [lo, hi] window with the invariant the answer, if it exists, is inside is the template that powers dozens of harder problems: boundary finding, rotated arrays, and binary search on the answer.
lo = 0, hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2
if nums[mid] == target: return mid
if nums[mid] < target: lo = mid + 1 # target is right of mid
else: hi = mid - 1 # target is left of mid
return -1