Python / Language / Binary search

bisect.py

# Make a Bisection Search (or binary search), 
# similar to what you do in dictionary.
# You start in the middle of the list, then you search the second half
# https://github.com/AllenDowney/ThinkPython2/blob/master/code/words.txt


# Word List
words = []
for line in open("/var/www/python/words.txt"):
    word = line.strip()
    words.append(word)


# Full Search
def search(keyword, words):
    i = 0
    for word in words:
        i += 1
        if word == keyword:
            print(i)
            return True
    print(i)
    return False


# SOLUTION

# Bisect Search
def search_bisect(keyword, words, loops=0):

    loops += 1
    i = len(words) // 2  # Look Here
    
    if words[i] == word: 
        print(loops)
        return True

    if word < words[i]:  
        search_bisect(keyword, words[:i], loops)
    else: 
        search_bisect(keyword, words[i+1:], loops)

    return False


search("mother", words) # 62889
search_bisect("mother", words)  # 16