StyleInCode

""" search_sorted_array.py - an experiment of approaches """

# usage: python3 search_sorted_array.py

import random


def naive(number, array):
    """ position of number in array, -1 if not found """
    assert array == sorted(array)
    for i, value in enumerate(array):
        if value == number:
            return i
    return -1


def tail_recursive(number, array):
    """ position of number in array, -1 if not found """
    assert array == sorted(array)
    if array == []:
        return -1
    if array[0] == number:
        return 0
    i = tail_recursive(number, array[1:])
    if i == -1:
        return -1
    return i + 1


def binary_iterative(number, array):
    """ position of number in array, -1 if not found """
    assert array == sorted(array)
    start, stop = 0, len(array) - 1
    while start <= stop:
        mid = (start + stop) // 2
        if array[mid] == number:
            return mid
        if array[mid] < number:
            start = mid + 1
        else:
            stop = mid - 1
    return -1


def binary_recursive(number, array, start=0, stop=None):
    """ position of number in array, -1 if not found """
    assert array == sorted(array)
    if stop is None:
        stop = len(array) - 1
    if start > stop:
        return -1
    mid = (start + stop) // 2
    if array[mid] == number:
        return mid
    if array[mid] < number:
        return binary_recursive(number, array, mid + 1, stop)
    return binary_recursive(number, array, start, mid - 1)


def monte_carlo(number, array):  # just for fun
    """ position of number in array, -1 if not found """
    assert array == sorted(array)
    indexes = list(range(len(array)))
    random.shuffle(indexes)
    start, stop = 0, len(array) - 1
    while indexes:
        i = indexes.pop()
        if i < start or i > stop:
            continue
        if array[i] == number:
            return i
        if array[i] < number:
            start = i
        else:
            stop = i
    return -1


if __name__ == '__main__':

    for search in [naive, tail_recursive, binary_iterative,
                   binary_recursive, monte_carlo]:
        try:
            search(0, [1, 3, 2])
        except AssertionError:
            pass
        else:
            raise AssertionError('Array is not sorted.')

        assert search(0, []) == -1
        assert search(0, [0]) == 0
        assert search(1, [0]) == -1
        assert search(0, [0, 1, 2]) == 0
        assert search(1, [0, 1, 2]) == 1
        assert search(2, [0, 1, 2]) == 2
        assert search(3, [0, 1, 2]) == -1
        assert search(0, list(range(100))) == 0
        assert search(55, list(range(100))) == 55
        assert search(99, list(range(100))) == 99

        print('tests passed', search)