7

Having a sorted list and some random value, I would like to find in which range the value is.

List goes like this: [0, 5, 10, 15, 20] And value is, say 8.

The standard way would be to either go from start until we hit value that is bigger than ours (like in the example below), or to perform binary search. 

grid = [0, 5, 10, 15, 20]
value = 8
result_index = 0
while result_index < len(grid) and grid[result_index] < value:
    result_index += 1

print result_index

I am wondering if there is a more pythonic approach, as this although short, looks bit of an eye sore. Thank you for your time!

tm_lv
  • 6,442
  • 5
  • 24
  • 16

2 Answers2

19
>>> import bisect
>>> grid = [0, 5, 10, 15, 20]
>>> value = 8
>>> bisect.bisect(grid, value)
2

Edit:

bisect — Array bisection algorithm

Alex Brasetvik
  • 11,218
  • 2
  • 35
  • 36
  • 1
    +1, beat me to it by ten seconds. Would be worth linking to the stdlib docs though. – Kiv Dec 19 '09 at 19:37
  • i guess i did not find the right terms to search with! Thank you very much, this is exactly what i was looking for! – tm_lv Dec 19 '09 at 19:39
  • O gosh, another WET language! :) funny to see how python (even though to suffering from a rigid type system as Java) nevertheless forces you to write everything twice. – akuhn Dec 19 '09 at 21:59
  • Adrian, no-one is forcing you to write everything twice. If you intended it to be a joke, I didn't get it; if you meant it, you don't know Python well enough. – tzot Dec 20 '09 at 17:47
1
for min, max in zip(grid, grid[1:]): # [(0, 5), (5, 10), (10, 15), (15, 20), (20, 25)]
  if max <= value < min: #previously: if value in xrange(min, max):
    return min, max
raise ValueError("value out of range")
badp
  • 11,409
  • 3
  • 61
  • 89
  • What happens if `value=2, grid = [3, 2**30]` ? – Alex Brasetvik Dec 19 '09 at 20:28
  • If your grid is `[3, 2**30]` chances are you have worse trouble than this. The real problem of this solution is that it only works for integer values of `value`. – badp Dec 19 '09 at 20:41
  • Point is that generating all the possible values in the range is terribly inefficient compared to `value >= min and value <= max`. Also, what happens if `value=20`? – Alex Brasetvik Dec 19 '09 at 20:49
  • `xrange(15, 20)` will yield `15, 16, 17, 18, 19`, so the above should return `20, 25`. You do raise a point, however. The real corner case is `value = 25` where `None` will be returned. – badp Dec 19 '09 at 21:39
  • Oh, right, 25 is just in badp's example --- I didn't see that. :-) – Alex Brasetvik Dec 19 '09 at 22:26