Source code for pygorithm.searching.interpolation_search

"""
Author: SHARAD BHAT
Created On: 22nd August 2017

 - Best O(1)
 - Average O(log(logn))
 - Worst O(n)
"""

import inspect

def search(_list, target):
    """
    This function performs an interpolation search
    on a sorted list and returns the index
    of item if successful else returns False

    :param _list: list to search
    :param target: item to search for
    :return: index of item if successful else returns False
    """

    if type(_list) is not list:
        raise TypeError("interpolation search only accepts lists, not {}".format(str(type(_list))))

    # First element
    low = 0
    # Last element
    high = len(_list) - 1

    # List is assumed to be sorted
    while low <= high and target >= _list[low] and target <= _list[high]:
        position = low + int(((float(high - low) / (_list[high] - _list[low])) * (target - _list[low])))

        if _list[position] == target:
            return position

        # If target is greater, search in right half
        if _list[position] < target:
            low = position + 1

        # If target is smaller, search in left half
        else:
            high = position - 1

    return False



def time_complexities():
    """
    Return information on functions
    time complexity
    :return: string
    """
    return "Best Case: O(1), Average Case: O(log(logn)), Worst Case: O(logn)"


def get_code():
    """
    easily retrieve the source code
    of the function
    :return: source code
    """
    return inspect.getsource(search)