# -*- coding: utf-8 -*-

"""二分查找"""


def binary_search(array, value):
    if not array:
        return -1
    begin = 0
    end = len(array) - 1
    while end >= begin:
        mid = int((begin + end) / 2)
        if array[mid] == value:
            return value
        elif array[mid] > value:
            end = mid - 1
        else:
            begin = mid + 1

    return -1


def test():
    a = [i for i in range(100)]

    assert binary_search(a, 32) == 32
    assert binary_search(a, 0) == 0
    assert binary_search(a, 109) == -1


"""二分查找的遞歸實現(xiàn)1"""


def binary_search_2(start, end, array, value):
    if end > start:
        mid = int((start + end) / 2)
        if array[mid] == value:
            return value
        elif array[mid] > value:
            return binary_search_2(start, mid - 1, array, value)
        else:
            return binary_search_2(mid + 1, end, array, value)
    return -1


def test2():
    a = list(range(100))
    assert binary_search_2(0, len(a), a, 78) == 78
    assert binary_search_2(0, len(a), a, 109) == -1


def binary_search3(array, value):
    if len(array):
        mid = int((0 + len(array)) / 2)
        if array[mid] == value:
            return value
        elif array[mid] > value:
            return binary_search3(array[0:mid + 1], value)
        else:
            return binary_search3(array[mid + 1:len(array)], value)
    return -1


def test3():
    a3 = list(range(100))
    assert binary_search3(a3, 78) == 78
    assert binary_search3(a3, 109) == -1