[Tutor] Binary search question
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
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.
Author of the Learn to Program web site
More information about the Tutor