Welcome, guest | Sign In | My Account | Store | Cart

Sometimes it is useful to know what is the smallest value in a sequence greater than (or equal to) some other value. Eg.

max_lt([2, 3, 5, 7, 11], 6) would be 5, because 5 is greatest value in the list which is also less than 6. Following the same lines method call min_gt([3, 5, 6, 10, 12], 6) would return 10, because 10 is the smallest value in the list greater than 6. The following four simple methods implement min_gt, min_le, max_gt and max_ge, but the input must be sorted for them to work.

However, Greg Jorgensen's suggestion is much more clever. No need for sorting, just use list comprehensions with min/max.

Python, 66 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66``` ```def min_gt(seq, val): """ Return smallest item in seq for which item > val applies. None is returned if seq was empty or all items in seq were <= val. >>> min_gt([1, 3, 6, 7], 4) 6 >>> min_gt([2, 4, 7, 11], 5) 7 """ for v in seq: if v > val: return v return None def min_ge(seq, val): """ Same as min_gt() except items equal to val are accepted as well. >>> min_ge([1, 3, 6, 7], 6) 6 >>> min_ge([2, 3, 4, 8], 8) 8 """ for v in seq: if v >= val: return v return None def max_lt(seq, val): """ Return greatest item in seq for which item < val applies. None is returned if seq was empty or all items in seq were >= val. >>> max_lt([3, 6, 7, 11], 10) 7 >>> max_lt((5, 9, 12, 13), 12) 9 """ idx = len(seq)-1 while idx >= 0: if seq[idx] < val: return seq[idx] idx -= 1 return None def max_le(seq, val): """ Same as max_lt(), but items in seq equal to val apply as well. >>> max_le([2, 3, 7, 11], 10) 7 >>> max_le((1, 3, 6, 11), 6) 6 """ idx = len(seq)-1 while idx >= 0: if seq[idx] <= val: return seq[idx] idx -= 1 return None ```

An example follows:

<pre> percentages = range(0, 100, 5) # all percentages from 0 to 95 at 5-step intervals

#### give as large share for each object as possible, using those fixed percentages

items_to_share = 148

for obj in mycontainer: my_share = max_le(percentages, items_to_share/len(mycontainer)) # convert it to percentage my_share /= 100.0

obj.acquire_items(int(my_share*items_to_share)) </pre>

Now each object get as much items as possible so that total percentage is An example follows:

<pre> percentages = range(0, 100, 5) # all percentages from 0 to 95 at 5-step intervals

#### give as large share for each object as possible, using those fixed percentages

items_to_share = 148

for obj in mycontainer: my_share = max_le(percentages, items_to_share/len(mycontainer)) # convert it to percentage my_share /= 100.0

obj.acquire_items(int(my_share*items_to_share)) </pre>

Now each object get as much items as possible so that total percentage is Greg Jorgensen 16 years, 6 months ago

simpler recipes. The requirement that the sequences are sorted, and the use of len() in two of the functions, means that the functions won't work on any iterable; they will only work on simple sequences. Try these more versatile functions that will work on any iterable, sorted or not:

``````def min_gt(seq, val):
return min([v for v in seq if v &gt; val])

def min_ge(seq, val):
return min([v for v in seq if v &gt;= val])

def max_lt(seq, val):
return max([v for v in seq if v &lt; val])

def max_le(seq, val):
return max([v for v in seq if v &lt;= val])
``````

If you want all values greater than or less than a specific value in a sequence, a list comprehension is a clear and concise technique:

``````[v for v in seq if v &gt; val]
``````

Once you have the resulting list, applying the min or max functions will extract the smallest or largest value. bearophile - 16 years, 6 months ago

Alternative. Removing the [] can be positive on the last versions of Python, for example:

``````def min_gt(seq, val):
return min(v for v in seq if v > val)

def min_ge(seq, val):
return min(v for v in seq if v >= val)
`````` Yair Chuchem 16 years, 6 months ago

bisect module. The standard module bisect does these stuff, and quickly too.

A useful module, You should get to know it. Yair Chuchem 16 years, 6 months ago

Binary search. The bisect module does the search with the binary search algorithm, which is O(log N). Instead of yours O(N) recipe. Larry Hastings 16 years, 6 months ago

Original recipe is broken. Sadly, this recipe needs to go back to the kitchen.

min_gt and min_ge will return the first value they find that is greater than (or possibly equal to) the value "val". min_gt([1, 3, 8, 7, 6], 6) returns 8, not 7. min_ge([2, 3, 4, 10, 8], 8) returns 10, not 8.

Also, min_ge() has a parameter "sorted=false" which isn't referenced anywhere in the recipe's body... what's up with that? Greg Jorgensen 16 years, 6 months ago

bisect suitable for some applications, not all. bisect only works on lists, not any iterable, and it requires that the list be sorted. If you have a sorted list, or something that can be turned into a sorted list, bisect is a good way to quickly find elements in the list. If you have arbitrary iterables or can't sort your list, bisect won't be much help. Edvard Majakari (author) 16 years, 6 months ago

Input must be sorted in examples. ..but forgot to mention in the docs. The remaining parameter sorted=False was in my first versions, where methods sorted input if it was needed. However, using

``````max([for i in items where i &lt; val])
``````

is far more clear and makes my recipe useless :)

I think the bisect module will be even better, though the list comprehension should be the easiest to understand. Qiangning Hong 16 years, 6 months ago

Just for completion... Rewrite the recipe using bisect module:

``````from bisect import bisect_left, bisect_right

def min_gt(seq, val):
return seq[bisect_right(seq, val)]

def min_ge(seq, val):
return seq[bisect_left(seq, val)]

def max_lt(seq, val):
return seq[bisect_left(seq, val) - 1]

def max_le(seq, val):
return seq[bisect_right(seq, val) - 1]
`````` Created by Edvard Majakari on Thu, 26 May 2005 (PSF)

### Required Modules

• (none specified)