First and last position of a value in a sorted list

Searching sorted data Mid-level Python 3.13+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank to get the last index of 5.

Python 3.13
from bisect import bisect_left, bisect_right
vals = [1, 5, 5, 5, 8]
first = bisect_left(vals, 5)
last = ____
print(first, last)

Options

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

Show answer

Answer: A bisect_right(vals, 5) - 1

Right: bisect_right lands just after the last 5.

The two bisect calls bracket the run of fives, so the last copy is one before the right bracket.

Why not the others?
  • B bisect_right(vals, 5). That is one past the last copy.
  • C bisect_left(vals, 5) + 1. That assumes exactly two copies.

30-second answer

Run two lower-bound searches: the first index with value >= target, and the first index with value >= target + 1 (for integers), minus one. If the first index is out of range or holds a different value, the target is absent. Two O(log n) searches and O(1) extra space.

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

Explain finding the first and last positions.

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

  • Two lower-bound searches
  • Check absent case
  • O(log n)

Deep dive

Reusing one lower-bound helper for both ends avoids writing two subtly different loops.

A linear scan from the first hit to the last is O(k) for k copies, which can be O(n).

For non-integer keys, use an upper-bound search (first value > target) instead of target + 1.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def first_and_last(vals: list[int], target: int) -> list[int]:
    def first_at_least(x: int) -> int:
        lo, hi = 0, len(vals)
        while lo < hi:
            mid = (lo + hi) // 2
            if vals[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    start = first_at_least(target)
    if start == len(vals) or vals[start] != target:
        return [-1, -1]
    return [start, first_at_least(target + 1) - 1]

Common mistakes

  • Finding one copy, then scanning outward, which is O(n) for long runs.
  • Forgetting the absent case.

Senior take & follow-ups

Mention reusing one helper twice; it shows you avoid duplicate off-by-one risks.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you count copies of the target?

    Show hint

    last - first + 1, or bisect_right minus bisect_left.

  2. What about a sorted list of strings?

    Show hint

    Use bisect_right for the end, since 'target + 1' does not apply.

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.