[Tutor] Binary search question

[Alan Gauld]

"Emile van Sebille" <emile at fenx.com> wrote 

> It's expensive enough that for a list this size I'd convert it to a dict 
> and use in on that.  eg,
> 
> a = range(100000)
> d = dict(zip(a,a))
> 

Surely that would depend on how often you do the search? 
If its a one off occurence I'd expect the overhead of zipping 
and converting to a dict would outweight the savings?

If the search was inside a loop however then I'd definitely 
agree. Although I'd opt for a set rather than a dict...

Another option would be to use the bisect module on a 
sorted version of the list.

if x in L

is like

L2 = sorted(L)
if L2[bisect.bisect_left(x)] == x      # untested! Might need bisect_right()...
But only testing and timing would tell which was faster.

HTH,


-- 
Alan Gauld
Author of the Learn to Program web site
http://www.alan-g.me.uk/