CODEWITHSUNDEEP
pythonlistsearchbinary-search
Jay Bell
Jay Bell

Reputation: 77

What search algorithm should I use if I need to find a value OR the next highest?

I will have an ordered list of Transaction ID's like this:

41025745
41025741
41025740
41025739
41025738
41025735
41025721
41025719
41025718
41025717
41025699
41025683
41025682
41025681

Anywhere from 10-1000 depending on how many I figure out I want to grab at a time based on API calls.

Say I want to find Transaction ID 41025735 (in the list) I could just use binary search to find it but if I want to find 41025736 (not in the list) I would return 41025738, the next highest value. What should I use? A modified Binary Search?

Upvotes: 1

Views: 65

Answers (2)

dawg
dawg

Reputation: 103844

Since your list is already sorted from largest to smallest, you do not need to sort. Here is an alternative that does not require presorting the list:

>>> data
['41025745', '41025741', '41025740', '41025739', '41025738', '41025735', '41025721', '41025719', '41025718', '41025717', '41025699', '41025683', '41025682', '41025681']
>>> def find_ge(li, item):
...     for e in reversed(li):
...         if e>=item:
...             return e
...      
...     raise ValueError  
>>> find_ge(data, '41025736')
'41025738'
>>> find_ge(data, '41025735')
'41025735'

Upvotes: -1

Raymond Hettinger
Raymond Hettinger

Reputation: 226316

The bisect module supports this directly but it requires that the input be in ascending order:

>>> from bisect import bisect_left

>>> data = '''\
41025745 41025741 41025740
41025739 41025738 41025735 41025721
41025719 41025718 41025717 41025699
41025683 41025682 41025681'''

>>> trans_ids = sorted(s.split())
>>> def find_ge(a, x):
        'Find leftmost item greater than or equal to x'
        i = bisect_left(a, x)
        if i != len(a):
            return a[i]
        raise ValueError

>>> find_ge(trans_ids, '41025736')
'41025738'

Upvotes: 3

Related Questions