binary_search.py

import random

def generate_name():
    """ generate a random first name with 3-6 letters,
        space, and family name with 4-8 letters """

    first=random.sample(alphabet ,random.randint(3,6))
    family=random.sample(alphabet ,random.randint(4,8))
    name=str.join("", first) + " " + str.join("", family)
    return str.title(name)


alphabet = 'abcdefghijklmnopqrstuvwxyz'

class Student:
    def __init__(self): 
        self.name = generate_name()
        self.id = random.randint(2*10**7,6*10**7)

    def __repr__(self):
        return  "<{name}, {id}>".format(**self.__dict__)

    def __eq__(self, other):
        return self.name == other.name \
               and self.id == other.id

    def __lt__(self, other):
        return self.name < other.name

    def is_given_name(self,word):
        return self.name.startswith(word+" ")


def students(n):
    return [ Student() for i in range(n)]


def binary_search(key,lst):
    """ iterative binary search
        lst better be sorted for binary search to work"""
    n = len(lst)
    lower = 0
    upper = n - 1
    outcome = None   # default value
    while lower <= upper:
        middle = (upper+lower) // 2
        if key == lst[middle].name:    # item found
            outcome = lst[middle]
            break  # gets out of the loop if key was found
        elif key < lst[middle].name:   # item cannot be in top half
            upper = middle - 1
        else:        # item cannot be in bottom half
            lower = middle + 1
    # if not outcome:  # holds when the key is not in the list
    # print(key, "not found")
    return outcome  



def rec_binary_search(key,lst,lower,upper):
    """ recursive binary search.
        passing lower and upper indices"""
    # print(lower,upper)   # for debugging purposes
    if lower > upper:
        return None
    elif lower == upper:
        if key == lst[lower].name:
            return lst[lower]
        else:
            return None
    elif key == lst[(lower+upper)//2].name:
        return lst[(lower+upper)//2]        
    elif key < lst[(lower+upper)//2].name:   # item cannot be in top half
        return rec_binary_search(key, lst, lower, (lower+upper)//2-1)
    else:        # item cannot be in bottom half
        return rec_binary_search(key, lst, (lower+upper)//2+1, upper)


def rec_slice_binary_search(key,lst):
    """ recursive binary search.
        passing sliced list"""
    n = len(lst)
    if n <= 0:
        return None
    elif n == 1:
        if key == lst[0].name:
            return lst[0]
        else:
            return None
    elif key == lst[n//2].name:
        return lst[n//2]        
    elif key < lst[n//2].name:   # item cannot be in top half
        return rec_slice_binary_search(key,lst[0:n//2])
    else:        # item cannot be in bottom half
        return rec_slice_binary_search(key,lst[n//2:n])


def disp_slice_rec_binary_search(key,lst):
    """ recursive binary search, displaying intermediate results.
        passing sliced """
    n = len(lst)
    print(n, lst[n//2])
    if n <= 0:
        print(key," not found")
        return None
    elif n == 1:
        if key == lst[0].name:
            return lst[0]
        else:
            print(key, " not found")
            return None
    elif key == lst[n//2].name:
        return lst[n//2]        
    elif key < lst[n//2].name:   # item cannot be in top half
        return disp_slice_rec_binary_search(key, lst[0:n//2])
    else:        # item cannot be in bottom half
        return disp_slice_rec_binary_search(key, lst[n//2:n])