Does python provide functions for performing binary search on sorted lists, analogous to the std::lower_bound and std::upper_bound algorithms of the C++ Standard Library?
Asked
Active
Viewed 3.1k times
57
Leon
- 31,443
- 4
- 72
- 97
-
See also: https://stackoverflow.com/questions/212358 – Karl Knechtel Jul 30 '22 at 01:30
2 Answers
79
Those functions are located in the bisect module:
bisect.bisect_left(a, x, lo=0, hi=len(a)) is the analog of
std::lower_bound().bisect.bisect_right(a, x, lo=0, hi=len(a)) is the analog of
std::upper_bound().
Note: there is also a function bisect() which is an alias for bisect_right().
Leon
- 31,443
- 4
- 72
- 97
0
There is also sortedcontainers package in python, which also has bisect_left and bisect_right. https://grantjenks.com/docs/sortedcontainers/sortedlist.html
This could be handy if you don't want to maintain the list sorted yourself (e.g. insertion).
Mircea
- 954
- 1
- 13
- 17