python - Why is my implementation of binary search very inefficient? -

python - Why is my implementation of binary search very inefficient? -

i doing python exercise search word given sorted wordlist, containing more 100,000 words.

when using bisect_left python bisect module, efficient, using binary method created myself inefficient. please clarify why？

this searching method using python bisect module:

def in_bisect(word_list, word): """checks whether word in list using bisection search. precondition: words in list sorted word_list: list of strings word: string """ = bisect_left(word_list, word) if != len(word_list) , word_list[i] == word: homecoming true else: homecoming false

my implementation inefficient (don't know why):

def my_bisect(wordlist,word): """search given word in wordlist using bisection search, known binary search """ if len(wordlist) == 0: homecoming false if len(wordlist) == 1: if wordlist[0] == word: homecoming true else: homecoming false if word in wordlist[len(wordlist)/2:]: homecoming true homecoming my_bisect(wordlist[len(wordlist)/2:],word)

if word in wordlist[len(wordlist)/2:]

will create python search through half of wordlist, kinda defeating purpose of writing binary search in first place. also, not splitting list in half correctly. strategy binary search cutting search space in half each step, , apply same strategy half word could in. in order know half right 1 search, critical wordlist sorted. here's sample implementation keeps track of number of calls needed verify whether word in wordlist.

import random numcalls = 0 def bs(wordlist, word): # increment numcalls print('wordlist',wordlist) global numcalls numcalls += 1 # base of operations cases if not wordlist: homecoming false length = len(wordlist) if length == 1: homecoming wordlist[0] == word # split list in half mid = int(length/2) # mid index leftlist = wordlist[:mid] rightlist = wordlist[mid:] print('leftlist',leftlist) print('rightlist',rightlist) print() # recursion if word < rightlist[0]: homecoming bs(leftlist, word) # word can in left list homecoming bs(rightlist, word) # word can in right list alphabet = 'abcdefghijklmnopqrstuvwxyz' wl = sorted(random.sample(alphabet, 10)) print(bs(wl, 'm')) print(numcalls)

i included print statements can see going on. here 2 sample outputs. first: word in wordlist:

wordlist ['b', 'c', 'g', 'i', 'l', 'm', 'n', 'r', 's', 'v'] leftlist ['b', 'c', 'g', 'i', 'l'] rightlist ['m', 'n', 'r', 's', 'v'] wordlist ['m', 'n', 'r', 's', 'v'] leftlist ['m', 'n'] rightlist ['r', 's', 'v'] wordlist ['m', 'n'] leftlist ['m'] rightlist ['n'] wordlist ['m'] true 4

second: word not in wordlist:

wordlist ['a', 'c', 'd', 'e', 'g', 'l', 'o', 'q', 't', 'x'] leftlist ['a', 'c', 'd', 'e', 'g'] rightlist ['l', 'o', 'q', 't', 'x'] wordlist ['l', 'o', 'q', 't', 'x'] leftlist ['l', 'o'] rightlist ['q', 't', 'x'] wordlist ['l', 'o'] leftlist ['l'] rightlist ['o'] wordlist ['l'] false 4

note if double size of wordlist, i.e. use

wl = sorted(random.sample(alphabet, 20))

numcalls on average 1 higher wordlist of length 10, because wordlist has split in half 1 time more.

python recursion binary-search