Find an Item in a Sorted List

Mike C. Fletcher mcfletch at geocities.com
Wed Feb 27 01:40:40 CET 2002


See standard module bisect:

# untested...
lines = open( file ).readlines()
# name is < name+',number'
import bisect
index = bisect.bisect( lines, name )
if index+1 < len(lines):
	line = lines[index+1]
	if line[:len(name)+1] == name+',':
		do_stuff_with_line(line)

For your own solution:
	for loop would likely be faster than filter, as it only needs to check 
until it matches or the values become > the test value

HTH,
Mike

HankC wrote:
> Greetings:
> 
> I'm 2 days new to Python and hope I can get some pointers here...
> 
> I have a sorted, delimited text file such as:
> 
> Arty,1000
> Bobby,2000
> Charlie,3000
> 
> Knowing a name, I want to return the entire line from the file.  My
> approach/problems (any comments appreciated):
> 
> # use the filter method
> # filter fxn
> def Match(line): return line[:toklen] == tok
> 
> # find match fxn
> def FindMatch:
> 	fp = open(fname)
> 	flist = fp.readlines()
> 	dataline = filter(Match, eodflist)
> 
> My problem is that I don't understand how, if it's even possible, to
> set tok and toklen values in the FindMatch fxn and pass them to Match.
> Is it possible to pass multiple values to the function used by
> filter()?
> 
> More general...  does filter() have any performance advantage over
> just using a for loop?  The datafile list has 10,000+ items.  My
> background is in object pascal where I would read the items into a
> list then use a binary search to find the target.  I'm hoping there's
> an efficient python method to perform a search easily on a sorted
> list.
> 
> Suppose I want to make tok and toklen global to the module.  Is this
> possible?
> 
> TIA!
> 


-- 
_______________________________________
   Mike C. Fletcher
   http://members.rogers.com/mcfletch/






More information about the Python-list mailing list