The problem
Given a list of numbers sorted from small to large and a target number, return the position of the target, or −1 if it is not in the list.
Input: [3,7,12,18,23,29,34,38,42,47,51,56,63,70,77], target = 42 Output: 8 (positions count from 0)
Picture it
Picture a long library shelf where books are arranged by number. Instead of checking books one by one, pull out the middle book. If its number is too small, the book you want must be in the right half, so you can ignore the whole left half. Too big? Ignore the right half. Each look throws away half the shelf, so even 1,000 books need only about 10 looks.
How to recognise it
- The input is sorted, and you are looking for a value or a position.
- One comparison with a middle item tells you which half cannot contain the answer, so you can throw that half away.
- The problem asks for O(log n) time, which almost always means binary search.
- The same idea works on anything with a yes/no test that flips once from "too small" to "big enough": positions in a list, a speed, a capacity, a time.
Start with brute force
Walk through the list from the start and return the first position that holds the target.
def search_brute(books, target):
for i, x in enumerate(books):
if x == target:
return i
return -1
Time is O(n) and space is O(1). With LeetCode's limit of 10^4 numbers that is only 10^4 comparisons, so it would pass the tests, but the problem explicitly asks for O(log n). Binary search needs about 14 comparisons for 10^4 numbers, and about 30 for 10^9. The gap matters when the list is huge or you search it many times.
From brute force to the idea
- Find the waste. A linear scan ignores the fact that the list is sorted. Comparing the target with any one item tells you whether the target is to the left or the right of it.
- Compare with the middle. Keep an inclusive range
lo..hiwhere the target could still be. Look atmid = (lo + hi) // 2. - Discard half. If
books[mid] == target, returnmid. Ifbooks[mid] < target, everything up tomidis too small, solo = mid + 1. Otherwise everything frommidon is too big, sohi = mid - 1. - Always move past
mid. Becausemidhas been checked, the new range excludes it. That is what guarantees the range shrinks every step and the loop ends. - Stop when the range is empty. The loop runs
while lo <= hi. Whenlo > hino position is left, so return −1.
This is the key idea: each comparison with the middle item rules out half of the remaining positions.
The key idea
Keep a range [lo, hi] that must contain the answer and halve it every step: O(log n).
Python solution
def search(books, target):
lo, hi = 0, len(books) - 1
while lo <= hi:
mid = (lo + hi) // 2
if books[mid] == target:
return mid
if books[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n): may compare with every item | O(1) |
| Binary search (shown code) | O(log n): the range halves every step, so about log2(n) + 1 comparisons at most | O(1): only lo, hi and mid |
Edge cases
- Empty list:
histarts at −1, the loop never runs, returns −1. LeetCode promises at least one number. - One number (
[5], target 5):lo == hi == 0, so the loop must use<=; returns 0. - Target smaller or larger than everything (
[1, 3]with 0 or 4): the range empties off one end and the function returns −1. - The example (target 42): returns 8.
- Duplicates (
[2, 2, 2, 2, 2], target 2): returns 2, the first middle that matches, not the first copy. The problem has unique values; for the first copy use the lower-bound version below. - Overflow: Python integers cannot overflow. In Java or C++ write
lo + (hi - lo) / 2, becauselo + hican exceed the integer limit on very large arrays.
Common mistakes
- Writing
while lo < hiwith an inclusivehi. When one candidate is left it is never checked, so[5]with target 5 returns −1. - Setting
lo = midinstead ofmid + 1. With two items left,midequalslo, the range stops shrinking, and the loop never ends. - Starting with
hi = len(books)but keepingwhile lo <= hi. Searching[1]for 5 then readsbooks[1]and raisesIndexError.
Return the first position whose value is at least the target. If the target is present that is its first copy; if not, it is where it would be inserted to keep the list sorted. For [1, 3, 5] and target 4 the answer is 2; for target 9 it is 3. Describe your approach, then write it if you like.
Compare with our answer
Search for a boundary instead of a value. Use a half-open range lo..hi with hi = len(a), because the answer can be just past the end. If a[mid] < target, the answer is to the right of mid; otherwise mid itself might be the answer, so keep it with hi = mid.
def first_at_least(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
first_at_least([2, 2, 2, 2, 2], 2) is 0. This is what Python's bisect.bisect_left does. Time O(log n), space O(1).
A strong answer mentions: why hi starts at len(a), why hi = mid (not mid - 1) keeps a possible answer, and why while lo < hi ends with lo == hi as the answer.
1. A log file has one line per second, sorted by timestamp. You must find the first line at or after 10:00. Which approach fits best?
The lines are sorted, so a lower-bound binary search finds the boundary in O(log n). A dictionary lookup fails when no line has exactly 10:00, and jumping by 60 is still linear in the file size.
2. The shown code searches 10^6 sorted numbers. About how many comparisons does it need in the worst case?
Each step halves the remaining range, so it takes about log2(10^6) ≈ 20 steps. Half a million is the average for a linear scan, not for binary search.
3. A learner writes while lo < hi: and keeps the rest of the shown code. Which call now returns a wrong answer?
With one item, lo == hi == 0, so the loop never runs and −1 is returned. In [1, 3, 5] the 3 is found at the first middle, and the missing targets return −1 either way.
Score 60% or more and the lesson is marked complete.