10

I have a question from algorithm point of view. 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 (lets say) 4.. So the answer is 4.9 But besides the obvious solution.. (iterating thru list and keeping a track of smallest number greater than k) what is the "pythonic way" to do this. Thanks

frazman
  • 32,081
  • 75
  • 184
  • 269

4 Answers4

23
min(x for x in my_list if x > 4)
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • Granted, this does exactly what you stated in the OP ("iterate through the list keeping track of the smallest number greater than k") - it's just a compact way of writing it. – Amber Nov 12 '11 at 00:52
  • @Amber: Well, what else should you do? :) – Sven Marnach Nov 12 '11 at 00:55
  • 4
    @SvenMarnach - I wasn't saying there was anything wrong with your answer (there's literally nothing better you could do); just pointing out to the asker that this is just syntactic sugar, not something that's magically more efficient than iteration. – Amber Nov 12 '11 at 00:58
  • I just had the same question. Reading the accepted answer kinda depressed me - who wants to go digging elsewhere - and then I saw this. Syntactic sugar or not, it's still sweet. – Noich Nov 11 '15 at 18:50
9

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

See Python binary search-like function to find first number in sorted list greater than a specific value

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

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

Community
  • 1
  • 1
DNA
  • 42,007
  • 12
  • 107
  • 146
7

This is a perfect scenario 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 could also use list comprehensions:

>>> 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 list comprehension seems to be less straight-forward on the first view, it is the recommended way to do it. According to some Python developers, filter should not be used.

A generator expression is even better because it doesn't create the list in memory:

>>> 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
Martin Thoma
  • 124,992
  • 159
  • 614
  • 958
  • 1
    A warning: min() will throw a ValueError if the iterable is empty (both for the filter function return value and list comprehension. To handle this, add an if/else to check that the iterable isn't empty and handle it if so. – Dave Liu Sep 11 '19 at 21:42
2

I've no idea about python, but from an algorithmic point of view maybe I can add something. In your example your list is monotonically increasing (sorted). If that is always true of your list, then a small optimization might be to stop iterating once you've reached a number larger than 4.

If your list always has few numbers lower than 4, this will be a great optimization, but if number of items before and after the target number is random, then this improvement isn't reliable.

In that case, you might want to search the list by partitioning it. Test if middle element is larger than 4. If it is larger, throw away upper half, otherwise throw away lower half. Do the same thing on the new half-length list. You need to deal with even and odd numbers and with the case when you have only 1 or 2 items left in the list-segment. For a large list, this should reduce the number of tests significantly.

Gaute Løken
  • 7,522
  • 3
  • 20
  • 38