Where would a new price go in a sorted list?

Searching sorted data Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from bisect import bisect_left, bisect_right
prices = [2, 4, 4, 7, 9]
left4 = bisect_left(prices, 4)
right4 = bisect_right(prices, 4)
print(left4, right4, bisect_left(prices, 10))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 1 3 5

Right: 4 first appears at 1, the copies end before 3, and 10 would go at the end.

The two bisect functions bracket every copy of a value, which is how counts and ranges are answered in O(log n).

Why not the others?
  • B 1 2 5. bisect_right goes past both copies of 4.
  • C 2 3 -1. bisect_left returns the first copy, and an insert position is never -1.
Lower-bound search on eight sorted prices: each step shows the range, the middle price and which half is kept, for targets 7 and 13.

Steps come from running the Python solution.

Text version

Target 7:

Cells: [2, 4, 4, 7, 9, 12, 15, 20]

Range: lo up to but not including hi.

  1. Lo 0, hi 8, mid = 4. a[4] = 9 >= 7: keep the left half
  2. Lo 0, hi 4, mid = 2. a[2] = 4 < 7: keep the right half
  3. Lo 3, hi 4, mid = 3. a[3] = 7 >= 7: keep the left half
  4. Lo 3, hi 3. Answer index = 3. First index with a value >= 7: 3

Result: 3

Target 13:

Cells: [2, 4, 4, 7, 9, 12, 15, 20]

Range: lo up to but not including hi.

  1. Lo 0, hi 8, mid = 4. a[4] = 9 < 13: keep the right half
  2. Lo 5, hi 8, mid = 6. a[6] = 15 >= 13: keep the left half
  3. Lo 5, hi 6, mid = 5. a[5] = 12 < 13: keep the right half
  4. Lo 6, hi 6. Answer index = 6. First index with a value >= 13: 6

Result: 6

30-second answer

Binary search with a half-open range. Keep the invariant that the answer lies in [lo, hi]: if prices[mid] is below the target, the answer is right of mid, so lo = mid + 1; otherwise mid itself could be the answer, so hi = mid. The range halves each step, giving O(log n) time and O(1) space.

Practise saying it · 45 s. No recording, just a timer

Explain lower-bound binary search.

Say your answer out loud, then check which of these points you covered:

  • Half-open range [lo, hi]
  • lo = mid + 1 or hi = mid
  • O(log n)

Deep dive

This 'lower bound' is the building block for most binary search questions: first occurrence, insert position, counting values in a range.

hi = len(prices) (not len - 1) lets the answer be 'after everything'.

In Python, bisect.bisect_left does exactly this.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def first_at_least(prices: list[int], target: int) -> int:
    lo, hi = 0, len(prices)  # the answer is always in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid  # mid itself may be the answer
    return lo

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun firstAtLeast(prices: List<Int>, target: Int): Int {
    var lo = 0
    var hi = prices.size
    while (lo < hi) {
        val mid = (lo + hi) ushr 1
        if (prices[mid] < target) {
            lo = mid + 1
        } else {
            hi = mid // mid itself may be the answer
        }
    }
    return lo
}

Common mistakes

  • Mixing hi = mid with while lo <= hi, which can loop forever.
  • Returning -1 when the target is larger than every price instead of the length.

Senior take & follow-ups

State the invariant in words before writing the loop. It is how you avoid off-by-one errors under pressure.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the last index with price at most x?

    Show hint

    Lower bound of x + 1 (for integers), minus 1.

  2. How do you count prices in [a, b]?

    Show hint

    Lower bound of b + 1 minus lower bound of a.

See it animated on iPhone (Binary Search in DSA Master - Data & Algorithms)

What each operation costs: Binary Search · Linear Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.