help retrieving / storing info in dictionary or gadfly
Sune Kirkeby
sune at interspace.dk
Thu Jan 18 07:46:44 EST 2001
[ "Bryan Webb" <bww00 at amdahl.com> ]
> I have a dictionary that has records with keys from 1 to 2^128 I
> can build a list and sort the keys in order, then search thru the
> list of sorted keys.
> If the list has 1,2,3,4,5,7,8,9 and I need to search for 6. 6 is
> not in the list , so I need the record that is closest to 6 but not
> greater than 6. Is there a way to further index the list of keys to
> do this ?
Since the list is sorted (in ascending order, presumably), you could
just do a binary search through it. Something along the lines of,
def find(list, number):
"""Given a list of numbers, sorted in ascending order, find the
largest element that is less-than-or-equal some given number. If a
fitting element is found return this (the value, that is);
otherwise it return None."""
# Sanity check
if len(list) == 0:
return None
# Simple binary search through the list.
pivot = len(list) / 2
while list[pivot] != number:
# If the pivot is less-than the sought-for number we include
# the pivot in the further search (so we can find the nearest
# number that is less-than, if no exact match is found).
if list[pivot] < number:
list = list[pivot : ]
else:
list = list[0 : pivot]
pivot = len(list) / 2
if len(list) == 1:
break
# Done, if list[pivot] > number we searched all the way down to the
# bottom of the list, but found no match, so we return None since
# all elements in the list are greater-than the number.
if list[pivot] <= number:
return list[pivot]
else:
return None
> Could I use GADFLY to do this.
Dunno.
--
Sune Kirkeby | "Imagine, if you will, that there were no
http://mel.interspace.dk/~sune/ | such thing as a hypothetical situation..."
More information about the Python-list
mailing list