[Tutor] Binary search question

Alan Gauld alan.gauld at btinternet.com
Fri Apr 23 23:21:13 CEST 2010

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


Alan Gauld
Author of the Learn to Program web site

More information about the Tutor mailing list