Binary Search using Python

binary_search.py

def binary_search(a_list, search_item):

    """
    Binary search using loop on a sorted list

    Based on the value we look for, bifurcate the list into two look up windows. 
    The value we look for is the middle value of current window. 
    
    If search value < middle value of the window, put the upper bound to middle value
    If search value > middle value of the window, put the lower bound to middle value
    
    If search value == middle value of the window, item is found.

    If lower bound > upper bound, the list limits are out of index. We can stop the search. 
    """
    
    low = 0
    high = len(a_list) - 1 
    
    while low <= high:

        mid = (high+low)//2
        
        if a_list[mid] == search_item:
            return mid + 1
	
        else:
            if search_item > a_list[mid]:
                low = mid + 1
            else:
                high = mid - 1
    return -1


def binary_search2(a_list, search_item, low, high):

    """
    Binary search using recursion

    """ 

    if low <= high:
        mid = (high+low)//2
        
        if a_list[mid] == search_item:
            return mid + 1
        else:
            if search_item > a_list[mid]:
                return binary_search2(a_list, search_item, mid+1, high)
            else:
                return binary_search2(a_list, search_item, low, mid - 1)
    return -1 


# a_list = [1, -2,3,4,5]

# search_item = 4

# print(binary_search2(a_list, search_item, 0, len(a_list)-1))

# search_item = 5

# print(binary_search2(a_list, search_item, 0, len(a_list)))

# search_item = 2

# print(binary_search2(a_list, search_item, 0, len(a_list)))

# search_item = -1

# print(binary_search2(a_list, search_item, 0, len(a_list)))


# search_item = 8

# print(binary_search2(a_list, search_item, 0, len(a_list)-1))