Binary Search

binary_search.py

def binary_search(arr, val, algo='iterative'):
    '''
    Wrapper function for binary search routine. By default, choses the iterative
    variant of the binary search algorithm. 

    Input : Sorted Array
    Output: Index of 'val' being searched is printed on console. If not found, -1 
    is printed.
    '''

    algos = {'iterative': binary_search_iterative, 'recursive': binary_search_recursive}
    if algo in algos:
        print algos[algo](arr, 0, len(arr)-1, val)
    else:
        print "Invalid algo type entered!"

def binary_search_iterative(arr, low, high, val):
    '''
    Binary search - iterative version

    Time complexity for search: O(log(n))
    Space complexity for search: O(1)
    '''

    if not arr:
        return -1
    while low <= high:
        mid = (low + high) / 2
        if arr[mid] == val:
            return mid
        elif arr[mid] < val:
            low = mid + 1
        else:
            high = mid - 1
    return -1


def binary_search_recursive(arr, low, high, val):
    '''
    Binary search - recursive version

    Time complexity for search: O(log(n))
    Space complexity for search: O(h) (h == height of recurrence tree)
    '''
    if not arr or low > high:
        return -1

    mid = (low + high) / 2
    if arr[mid] == val:
        return mid
    elif arr[mid] > val:
        return binary_search_recursive(arr, low, mid-1, val)
    else:
        return binary_search_recursive(arr, mid+1, high, val)