[Tutor] binary vs. linear search

[Sean 'Shaleh' Perry]

On Friday 23 August 2002 06:57 pm, Tim Wilson wrote:
>
> Here are the two algorithms:
>
> def isWord(word, wordList):    # binary search
>     wordList.sort()
>     item_insert_point =3D bisect.bisect(wordList, word)
>     is_present =3D wordList[item_insert_point-1:item_insert_point] =3D=3D
> [word]
>     if is_present:
>         return 1
>     return 0
>
>
> def isWord(word, wordList):    # regular python search
>     if word in wordList:
>         return 1
>     return 0
>
>
> The results for looking for 6,175 words in a list of 45,392 words are:
>
> binary:  3m 25s
> regular: 2m 58s
>
> I was surprised to find the binary search slower in this case. Can
> anyone explain why?
>

The binary search does more work.  You call list.sort(), bisect() and eve=
n do=20
a list splice.  To make it truly fair passing the two functions a sorted=20
list.