Run it
Both boundaries, and the three questions one pair of calls answers.
By hand: the two loops differ by a single character.
Absent values, and the key= parameter that does not transform the needle.
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 lodef 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.
What to say 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.
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.
The follow-ups interviewers ask
"Count occurrences of a value." bisect_right - bisect_left. Same two calls, third question answered for free, and it is the most common follow-up.
"Insert while keeping the list sorted." bisect.insort, which is bisect_left plus a list insert - O(log n) to find and O(n) to shift. Worth saying that the search is not the expensive half.
"Search a list of records by one field." key= from Python 3.10, with the needle being the key value rather than a record. Before that, a parallel list of keys - which is still the right answer when the key is expensive, because key= is called on every probe.
"How would you find the number of elements less than x?" bisect_left(a, x), directly - the insertion point is that count, because everything before it is strictly smaller. The same call answers "how many are greater than x" as len(a) - bisect_right(a, x). Recognising that an insertion point is a count is worth more than the boundary problem itself; it is how range queries on sorted data get answered without a scan.
"What if the array is rotated, or sorted descending?" bisect assumes ascending order and returns nonsense otherwise, silently. For descending data the usual fix is to search a negated view or reverse the comparison in a hand-written loop; for rotated data the boundary search no longer applies at all, because the sequence is not monotonic.
Common wrong answers
"Find one occurrence, then scan outwards." O(n) in the worst case, which throws away the reason for binary searching. A run of a million identical values makes it a linear scan.
"bisect_right gives the last index." One past it. The off-by-one here is the single most common error in this question.
"If bisect_left returns a valid index, the value is present." It always returns a valid insertion point, including for values that are absent. The a[lo] != x check is not optional.
Recap in one screen
- 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.
- Worth trying: 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.
- Worth trying: 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.