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

python binary-search
Leon picture Leon · Jun 17, 2016 · Viewed 10.6k times · Source

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?

Answer

Leon picture Leon · Jun 17, 2016

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

Related questions

Binary search (bisection) in Python

Is there a library function that performs binary search on a list/tuple and return the position of the item if found and 'False' (-1, None, etc.) if not? I found the functions bisect_left/right in the bisect module, …

Read More
Binary search algorithm in python

I am trying to implement the binary search in python and have written it as follows. However, I can't make it stop whenever needle_element is larger than the largest element in the array. Can you help? Thanks. def binary_…

Read More
What is the performance impact of non-unique indexes in pandas?

From the pandas documentation, I've gathered that unique-valued indices make certain operations efficient, and that non-unique indices are occasionally tolerated. From the outside, it doesn't look like non-unique indices are taken advantage of in any way. For example, the following …

Read More