vizlearn

First and last position of a target

Interview QuestionsBy Updated

A plain binary search finds some occurrence, and which one depends on where mid landed. The boundaries need two searches: bisect_left for the first index where the value could go, bisect_right for one past the last. Together they bracket the run — and their difference is the count.

Binary searchCoding problemMedium

Step through it

What to watch

  • A plain search finds an arbitrary occurrence — that is why this needs a different loop.
  • bisect_right is one past the last, so the last index is right - 1.
  • When the value is absent the two are equal, which is the not-found test.

Say this out loud

"Two binary searches. bisect_left gives the first index where the value could be inserted, bisect_right gives one past the last, so the answer is left and right minus one. If left equals right the value is absent. Each is O(log n), and the difference between them is the count, which is usually the next thing I am asked for."

Overview

In a sorted array with duplicates, the first and last occurrence are insertion boundaries. Two binary searches find the left and right boundaries in O(log n), even when the target is missing.

Run it

Both boundaries, and the three questions one pair of calls answers.

1Python
Output
By hand: the two loops differ by a single character.
2Python
Output
Absent values, and the key= parameter that does not transform the needle.
3Python
Output

                

                

                    
Why a plain search is not enough

                    
With duplicates, the standard loop stops at whichever occurrence mid hit first. That is a correct answer to "is it there" and no answer at all to "where does the run start" — and scanning left from the hit is O(n) in the worst case, which throws away the reason for using binary search.
The fix is to stop searching for the value and start searching for the boundary. On finding a match, do not return: keep going in the direction of the edge you want. That is the only change, and it is what both bisect functions do.

                

                

                    
left and right, precisely

                    
bisect_left(a, x) returns the first index i such that a[i] >= x. So everything before it is strictly less than x, and if x is present, i is its first occurrence.
bisect_right(a, x) returns the first index i such that a[i] > x. So it is one past the last occurrence, and the last index is right - 1.
Three consequences, and they are why the pair is worth memorising. left == right means absent. right - left is the count. And a[left:right] is the run itself, as a slice.

                

                

                    
Writing it by hand

                    
The interviewer usually wants the loop, not the import. It is the half-open search from the previous question with one comparison changed:
def lower(a, x):          # bisect_left
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:  lo = mid + 1
        else:            hi = mid
    return lo
def upper(a, x):          # bisect_right lo, hi = 0, len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] <= x: lo = mid + 1   # <= is the only difference else:            hi = mid return lo
One character. < stops at the first element not less than x; <= steps over every element equal to it. Being able to point at that character and say what it does is the whole question.

                

                

                    
The key= trap

                    
bisect gained a key= parameter in Python 3.10, and it behaves differently from sorted(key=...) in a way that catches people: the needle is not passed through the key. So searching a list of records by one field means comparing against the field value directly, not against a record:
i = bisect_left(people, 30, key=lambda p: p.age)
Before 3.10 the standard workaround was to keep a parallel list of just the keys and search that — which is still what you do when the key is expensive to compute, because key= calls it on every probe.

                

                

                    
Edge cases to raise

                    
Volunteering these is most of what separates a correct answer from a good one.
Absent values. left == right, and the shared index is still useful - it is where the value would go.
A value larger than everything. bisect_left returns len(a), so indexing a[lo] raises. Check the bound before the equality.
The whole array is the value. left = 0 and right = len(a), so the last index is len(a) - 1 - worth checking, because it is where a missing minus-one shows up.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
Both boundaries from bisect and from the hand-written loops, the three questions one pair of calls answers, and the absent case.
How the code works
  1. if lo == len(a) or a[lo] != xThe not-found test. bisect_left always returns an insertion point, so it never tells you on its own whether the value is there.
  2. bisect.bisect_right(a, x) - 1The minus one is the whole reason people get this wrong. bisect_right is one past the run.
  3. if a[mid] <= x: lo = mid + 1The single character that turns a lower bound into an upper bound. <= steps over equal elements instead of stopping at them.
  4. bisect_left(people, 30, key=lambda p: p[1])The needle is the key value, not a record. This is the opposite of how sorted(key=...) works and it surprises everybody once.
Change one thing
  • Remove the a[lo] != x check and search for 3. You get (4, 3) — a last index before the first, which is what an unguarded insertion point looks like.
  • Build a parallel list of ages and bisect that instead of using key=. That is the pre-3.10 idiom and still the right one when the key is expensive.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. Why can't a plain binary search answer 'first occurrence'?
  2. What does bisect_right return?
  3. How do you tell that a value is absent?
  4. What is the only difference between the two hand-written loops?




        
    



 Cheat sheet
First and last position of a target
Find the first and last index of a target in a sorted array with duplicates. Run two binary searches and see how each boundary is located.
INTERVIEW · vizlearn.in/interview/first-and-last-position.html
More in Interview
InterviewBinary search on the answer, not the arrayInterviewClimbing stairs: the DP that is FibonacciInterviewCoin change, and why greedy is wrongInterviewLongest increasing subsequence, twice
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact