What are python's equivalents of std::lower_bound and std::upper_bound C++ algorithms?

Question

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?

Uncinus

See also: stackoverflow.com/questions/212358 – Snuffer

Answer 1

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().

Uncinus

Answer 2

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).

Tableware