bisect
The bisect module is Python's built-in binary search. You give it a sorted list and a value, and it tells you where that value belongs. Here's the whole thing in one block:
Every function here assumes the list is already sorted. If it isn't, you won't get an error. You'll just get wrong answers.
bisect_left vs bisect_right
O(log n)Both functions return an index where you could insert the value and keep the list sorted. They only disagree when the value is already in the list. bisect_left puts you before all the copies, and bisect_right puts you after them:
Note
bisect.bisect() is just another name for bisect_right. If you see it in someone's code, it's the right-hand version.
A handy trick falls out of this. The number of times a value shows up is bisect_right(nums, x) - bisect_left(nums, x). In the list above, that's 4 - 1 = 3 copies of 3.
First element >= x, and counting a range
O(log n)These come up a lot in interviews. Many problems boil down to "find the first thing that's at least x" or "how many things fall between a and b." Here's how each one maps to bisect:
- First element >= x:
nums[bisect_left(nums, x)] - First element > x:
nums[bisect_right(nums, x)] - Last element <= x:
nums[bisect_right(nums, x) - 1] - Count of elements in [a, b]:
bisect_right(nums, b) - bisect_left(nums, a)
Note
Watch the edges. If every element is smaller than x, bisect_left returns len(nums), and indexing with that throws an IndexError. Always check the index before you use it.
When to write your own binary search instead
bisect only searches a sorted list for a value. Lots of interview problems use binary search on something that isn't a plain sorted list. You might be searching a rotated array, or searching over possible answers (like the slowest speed that still finishes in time), or looking for the spot where a condition flips from false to true. bisect can't handle those, so you'll need to write the loop yourself.
It's also a good idea to ask before you use bisect. If the whole problem is "implement binary search," the interviewer wants to see you write it. If binary search is just one step of a bigger solution, most interviewers are happy to see bisect. Our Modified Binary Search pattern walks through how to write it by hand without off-by-one bugs.
insort: keep a list sorted
O(n)This one is occasionally useful. bisect.insort() finds the right spot and inserts the value there, so the list stays sorted as you add to it:
Don't be fooled by the binary search, though. Finding the spot is O(log n), but inserting into a list still shifts everything after it, so each insort is O(n). If you're adding lots of items and only need the smallest or largest, a heap is usually the better fit.
One more niche thing: in Python 3.10 and newer, every bisect function takes a key= argument, like sorted() does.