二分查找（非递归、递归）python实现

# -*- coding: utf-8 -*-
"""
@author: sato
@file: binary_search.py
@time: 2019-09-03 15:21

"""


def binary_search(array, key):
    """二分查找非递归"""
    if len(array) <= 1:
        if array[0] != key:
            return
    start = 0
    end = len(array) - 1
    while start <= end:
        mid = (end + start) // 2
        if key < array[mid]:
            end = mid - 1
        elif key > array[mid]:
            start = mid + 1
        else:
            return True


def binary_search(a, b):
    """非递归"""
    min = 0
    max = len(a) - 1
    if b in a:
        while True:
            centre = int((max + min) / 2)
            if a[centre] > b:
                max = centre - 1
            elif a[centre] < b:
                min = centre + 1
            elif a[centre] == b:
                return centre
    else:
        return 'b in not in a'


def binary_search_reduce(array, key):
    """二分查找，递归实现版本"""
    if len(array) == 0:
        return False
    mid = len(array) // 2
    if array[mid] == key:
        return True
    elif key < array[mid]:
        return binary_search_reduce(array[:mid], key)
    else:
        return binary_search_reduce(array[mid + 1:], key)


if __name__ == '__main__':
    # 二分查找的最优时间复杂度为O（1），最坏时间复杂度为O（log n）
    # 递归空间复杂度是：O(N)  非递归: O(1)
    # 使用场景： 在有序数组中寻找指定元素
    sorted_list = [1, 4, 5, 7, 8, 9, 10, 13, 15, 17, 19, 23, 35]
    assert binary_search(sorted_list, 1)
    assert binary_search(sorted_list, 10)
    assert binary_search(sorted_list, 35)
    assert binary_search_reduce(sorted_list, 1)
    assert binary_search_reduce(sorted_list, 13)
    assert binary_search_reduce(sorted_list, 35)