Menu
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?
664
std::lower_boundReturns an iterator pointing to the first element in the range [first,last) which does not compare less than val . The elements are compared using operator< for the first version, and comp for the second.
lower_bound in C++ The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns an iterator pointing to the next smallest number just greater than or equal to that number.
upper_bound() returns an iterator pointing to the first element in the range [first, last) that is greater than the value. If no such an element is found, return end(). lower_bound() returns an iterator pointing to the first element in the range [first, last) which is greater or equal to the value.
It performs all the operations as performed by the set data structure in STL in log(n) complexity.
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().
71
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
