Find next lower item in a sorted list

Question

let's say I have a sorted list of Floats. Now I'd like to get the index of the next lower item of a given value. The usual for-loop aprroach has a complexity of O(n). Since the list is sorted there must be a way to get the index with O(log n).

My O(n) approach:

index=0
for i,value in enumerate(mylist):
    if value>compareValue:
        index=i-1

Is there a datatype for solving that problem in O(log n)?

Answer 1

How about bisect?

>>> import bisect
>>> float_list = [1.0, 1.3, 2.3, 4.5]
>>> i = bisect.bisect_left(float_list, 2.5)
>>> index = i - 1
>>> index
2

You might have to handle the case of a search value less than or equal to the lowest / leftmost value in the list separately (index == -1 in this case).

Depending on which index you want to have in case of equality, you might have to use bisect_right instead.

Answer 2

You can do a binary search on an array/list to get the index of the object you're looking for and get the index below it to get the lower entry (given that there actually is a lower entry!).

See: Binary search (bisection) in Python

Be careful when comparing floating point numbers for equality!