Implement binary search on a sorted list in O(log n), halving the search range each step. See linear vs logarithmic growth side by side in the Complexity Lab.
The problem
nums is sorted ascending. Return the index of target, or -1 if it is not present. Aim for O(log n) — don't scan.
Examples
Example 1
Input
binary_search([1, 3, 5, 7, 9, 11], 7)
Expected output
3
Example 2
Input
binary_search([1, 3, 5], 4)
Expected output
-1
+ 4 hidden tests on Submit — first element, last element.
Edge cases to ask about
- Empty list
- Target at either end
- Target missing
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| Linear scan | O(n) | O(1) | Ignores the fact that the list is sorted. |
| bestHalve the range each step | O(log n) | O(1) | A million elements need about 20 steps. |
Walkthrough of the optimal approach (try it yourself first)
Compare with the middle element: equal → done; too small → search the right half (lo = mid + 1); too big → the left half (hi = mid - 1). Each step halves the range, so a million elements need about 20 comparisons.
Most bugs are off-by-one: use lo <= hi and always move past mid, or the loop never ends. Run the Complexity Lab and compare the flat log curve with linear search.
bisect.bisect_left is the standard-library version.
Complexity: O(log n) time, O(1) space. Each comparison throws away half of the remaining range, so after k steps only n / 2ᵏ elements are left.
Reveal the reference solution
def binary_search(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
The brute force, for comparison
def binary_search(nums, target): for i, x in enumerate(nums): if x == target: return i return -1
Follow-ups interviewers ask
- Find the FIRST occurrence when there are duplicates.
- Write it recursively.
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Binary Search in Python?
The optimal solution runs in O(log n) time and O(1) auxiliary space. Each comparison throws away half of the remaining range, so after k steps only n / 2ᵏ elements are left.
What is the brute-force approach, and how do you optimise it?
Linear scan: O(n) time, O(1) space. Ignores the fact that the list is sorted. Halve the range each step: O(log n) time, O(1) space. A million elements need about 20 steps.
What follow-up questions do interviewers ask about Binary Search in Python?
Find the FIRST occurrence when there are duplicates. Write it recursively.