Find an Item in a Sorted List

[Carel Fellinger]

HankC <hankc at nospam.com> wrote:
> Greetings:

> I'm 2 days new to Python and hope I can get some pointers here...

Welcome and enjoy.

> 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

this should be (assuming a reasanably up-to-date Python):

    def Match(line, tok): return line.startswith(tok + ",")


> # find match fxn
> def FindMatch:
> 	fp = open(fname)
> 	flist = fp.readlines()
> 	dataline = filter(Match, eodflist)

I don't see how this could work (what is eodflist?), but an
alternative might be:

    def FindMatch(fname, tok):
        key = tok + ","
        for line in open(fname):
            if line.startswith(key):
                return line

The loop will end on the first match found.  If this is not what you
wanted, but instead you're after *all* matching lines, how about:

    key = tok + ","
    matches = [ x for x in open(fname) if x.startswith(key) ]


> More general...  does filter() have any performance advantage over
> just using a for loop?  The datafile list has 10,000+ items.  My

Not if you use a non builtin function.

> 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.

Depending on the length of the list you might be better of with a linear
search where you stop reading from the file the moment the name maches.
Otherwise you could write your own binary search in python, but I leave
that as an excercise to you:)

> Suppose I want to make tok and toklen global to the module.  Is this
> possible?

Yes ofcourse, but I would strongly advice against it:)
-- 
groetjes, carel