Algorithm (Python): Find the smallest number greater than k

Question

I have a question in terms of algorithm. I have a list of numbers (floats)

1.22,3.2, 4.9,12.3.....and so on 

And I want to find the smallest number greater than (say) 4 .. Thus, the answer is 4.9 But apart from the obvious solution .. (iterating through the list and saving the track of the smallest number greater than k) what is the "pythonic path". Thanks

Answer 1

Binary search will be the standard way to deal with this, but only if the list is sorted, as the previous answer pointed out.

See Python's binary search function to find the first number in a sorted list greater than a certain value

and In Python, how do you find the index of the first value that exceeds a threshold value in a sorted list?

for a discussion of the module that does this for you: http://docs.python.org/library/bisect.html

Answer 2

 min(x for x in my_list if x > 4) 

Answer 3

This is the perfect script for filter .

 >>> L = [1.22, 3.2, 4.9, 12.3] >>> k = 4 >>> a = min(filter(lambda x: x > k, L)) >>> print(a) 4.9 

You can also use lists:

 >>> L = [1.22, 3.2, 4.9, 12.3] >>> k = 4 >>> a = min([element for element in L if element > k]) >>> print(a) 4.9 

Although the perception of the list appears to be less straightforward in the first submission, this is the recommended way to do this. According to some Python developers, filter should not be used.

Answer 4

I have no idea about python, but from an algorithmic point of view, maybe I can add something. In your example, your list is monotonously increasing (sorting). If this is always true for your list, then a little optimization may be to stop the repetition as soon as you reach a number greater than 4.

If your list always has a few digits below 4, this will be a great optimization, but if the number of elements before and after the target number is random, then this improvement is not reliable.

In this case, you may need to search the list by dividing it. Check if the middle element is larger than 4. If it is larger, discard the upper half, otherwise discard the lower half. Do the same in the new half-cut list. You need to deal with even and odd numbers and with the case when only 1 or 2 elements are left in the list segment. For a large list, this should significantly reduce the number of tests.