Function binary_search_by_recursion

searches/binary_search.py:88–123

Pure implementation of binary search algorithm in Python by recursion Be careful collection must be sorted, otherwise result will be unpredictable First recursion should be started with left=0 and right=(len(sorted_collection)-1) :param sorted_collection: some sorted collection wit

(sorted_collection, item, left, right)

    return None

def binary_search_by_recursion(sorted_collection, item, left, right):

    """Pure implementation of binary search algorithm in Python by recursion

    Be careful collection must be sorted, otherwise result will be
    unpredictable
    First recursion should be started with left=0 and right=(len(sorted_collection)-1)

    :param sorted_collection: some sorted collection with comparable items
    :param item: item value to search
    :return: index of found item or None if item is not found

    Examples:
    >>> binary_search_std_lib([0, 5, 7, 10, 15], 0)
    0

    >>> binary_search_std_lib([0, 5, 7, 10, 15], 15)
    4

    >>> binary_search_std_lib([0, 5, 7, 10, 15], 5)
    1

    >>> binary_search_std_lib([0, 5, 7, 10, 15], 6)

    """
    if (right < left):
        return None
    
    midpoint = left + (right - left) // 2

    if sorted_collection[midpoint] == item:
        return midpoint
    elif sorted_collection[midpoint] > item:
        return binary_search_by_recursion(sorted_collection, item, left, midpoint-1)
    else:
        return binary_search_by_recursion(sorted_collection, item, midpoint+1, right)
      
def __assert_sorted(collection):
    """Check if collection is sorted, if not - raises :py:class:`ValueError`