I am exploring the bisect module in Python. The entire purpose of the module is clear to me, and I now know how to use it. But Performance notes in the documentation state this:

Bisection is effective for searching ranges of values. For locating specific values, dictionaries are more performant.

What does it mean by "searching ranges of values"? The bisect has bisect_left() and bisect_right(), both of which accept single values to find indices for. Any explanation to the docs? Thanks.

CodePudding user response：

Python dictionaries are hashed, thus provide O(1) search/insert/delete time complexities while binary search is logarithmic.

When you search for a specific value looking up a dictionary is more performant than binary search. Binary search makes more sense if you also are looking for a range around a specific value. If you want the closest possible value to your search term for example. Or if you want to know how many elements are already before the position of the element that you are looking for. Or how many elements lie between 2 particular elements that you are looking up. Hashed dictionaries can't do that of course. As you can see, in a binary search, all elements are related to each other in terms of their total ordering (however it is defined for that particular type). This property of sorted lists enables binary search to act upon ranges. While in a hashed dictionary, the elements are unrelated to each other, except for when their hashes are exactly the same.

CodePudding user response：

I think it means it is more efficient to find a value inside a range [a, b]. If you need to find a value equal to c it will need to search inside the list. However, if you use a dictionary, you can find it in O(1) time without searching.