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?
Advertisement
Answer
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().