Binary Search
Problem statement
You're given a list of integers nums, sorted from smallest to largest, and a target value. Find the index of target in nums and return it. If target isn't anywhere in the list, return -1.
Because the list is sorted, you're asked to solve this in O(log n) time — a plain left-to-right scan of every element is not fast enough to satisfy the problem's requirement, even though it does give a correct answer.
Examples
Example 1
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Explanation: 9 sits at index 4 in the sorted list, so that index is returned.
Example 2
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1
Explanation: 2 does not appear anywhere in the list, so there is no index to return.
Hints
Approach
Optimal: Binary search
Intuition
Because the list is sorted, comparing target to the middle element tells you which half it could be in, if it's present at all: if target is smaller than the middle, it can only be to the left (everything at or after the middle is too big); if it's bigger, it can only be to the right. Either way, one comparison rules out half of the remaining range — that halving is what makes the search logarithmic instead of linear, and it's exactly the piece of information the brute force ignored.
Steps
- Set
low = 0andhigh = n - 1. - While
low <= high:- Compute
mid = low + (high - low) // 2(this avoids overflow in languages with fixed-size integers, unlike(low + high) // 2). - If
nums[mid] == target, returnmid. - If
nums[mid] < target, the target (if present) must be to the right, so setlow = mid + 1. - Otherwise, set
high = mid - 1.
- Compute
- If the loop ends without returning,
targetisn't innums— return-1.
Dry run
nums = [-1, 0, 3, 5, 9, 12], target = 9
| step | low | high | mid | nums[mid] | comparison |
|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 3 | 3 < 9 → search right, low = 3 |
| 2 | 3 | 5 | 4 | 9 | match → return 4 |
Edge cases: target = 2 never matches — low and high cross (low = 2, high = 1) and the loop exits, returning -1; a single-element list starts with low == high, so mid points at that one element and the loop still runs exactly once.
Complexity
Time O(log n) - every step throws away half of what's left to search, so the range shrinks from n to n/2 to n/4 and so on, reaching a single element after about log₂(n) steps. For 1,000,000 elements that's about 20 comparisons instead of up to a million.
Space O(1) - only a few index variables are kept, no matter how large `nums` is.
class Solution:
def search(self, nums: list[int], target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
if __name__ == "__main__":
print(Solution().search([-1, 0, 3, 5, 9, 12], 9)) # 4
print(Solution().search([-1, 0, 3, 5, 9, 12], 2)) # -1RecapThe whole problem in a few lines, for the night before
- Spot it: search for a value in a sorted array, and O(n) isn't fast enough
- Idea: compare target to the middle element and discard the half that can't contain it; repeat on the remaining range
- Cost: O(log n) time, O(1) space (iterative)
- Trap:
(low + high) // 2can overflow in fixed-width integer languages — uselow + (high - low) // 2; also get the loop condition (low <= high) and pointer updates (mid + 1/mid - 1) exactly right, or you'll loop forever or skip the answer
Interview follow-ups
What if the array has duplicate values and you need the first occurrence of target?
Use the same halving idea, but don't stop at the first match: when
nums[mid] == target, recordmidas a candidate answer and keep searching the left half (high = mid - 1) to see if an earlier occurrence exists. This still runs in O(log n) time, since it's still one binary search, just one that doesn't return immediately on a match.The array is sorted but rotated at an unknown pivot, like [5, 9, 12, -1, 0, 3]. How would you adapt this?
At each step, check which half —
lowtomid, ormidtohigh— is still sorted; because of how a rotation works, at least one of the two always is. Iftargetfalls inside that sorted half's value range, search there; otherwise search the other half. This keeps the O(log n) time but adds one extra comparison per step to figure out which half is currently sorted.
Frequently asked questions
In languages with a fixed-size integer type (like Java's int or C++'s int), low + high can overflow if both are close to the maximum representable value, wrapping around to a negative number and breaking the search. low + (high - low) / 2 never adds two large numbers together, so it can't overflow. Python's integers grow arbitrarily large, so this specific bug can't happen there, but writing it the safe way in every language is a good habit interviewers look for.
No. The entire trick depends on being able to discard half the array based on one comparison, which is only valid because everything on one side of mid is guaranteed to be no bigger (or no smaller) than nums[mid]. On an unsorted array that guarantee doesn't hold, so comparing target to the middle element tells you nothing about which half to search next.
Both run in O(log n) time, but the iterative version above uses O(1) extra space, while a recursive version uses O(log n) space for the call stack, since each recursive call stays on the stack until the base case is reached. Interviewers usually accept either, but the iterative version is the safer default to write, since it avoids any risk of a stack overflow on adversarial inputs.
low <= high is what allows the loop to check the case where exactly one element remains (low == high). Using low < high instead would skip checking that last remaining element, and the search could incorrectly return -1 even when the target is sitting right there.
Binary search on sorted data is a real building block, not just a textbook exercise: it's what backs bisect-style lookups in Python, finding the first failed deploy in a sorted list of timestamps, or searching sorted log offsets by time. Interviewers use this exact easy problem to check that you can implement the pattern correctly and get its boundary conditions right — an empty range, an off-by-one in low/high — before building on it in a harder follow-up.
