二分查找

　　二分查找的列表必须是有序列表。从列表中间开始查找，如果给定的值和中间值相等则查找成功；如果给定的值大于或者小于中间的值，则从表中大于或者小于中间值的那一半中查找，重复上面操作，直到查找成功，或者在某一步中查找区间为空，则查找失败。

　　代码实现

# -*- coding = utf-8 -*-
# @Author: Wchime
# @time: 2023/1/27 15:35
# @file: 二分查找.py

def search_binary_not_recursion(li, item):
    """
    二分查找，非递归方法
    :param li:
    :param item:
    :return:
    """
    n = len(li)
    left = 0
    right = n-1
    while left <= right:
        mid = (left+right) // 2

        if li[mid] == item:
            return True
        elif item > li[mid]:
            left = mid + 1
        else:
            right = mid - 1
    return False


def serrch_binary_recursion(li, item):
    """
    二分查找，递归方式
    :param li:
    :param item:
    :return:
    """

    n = len(li)
    mid = n // 2
    if n > 0:
        if li[mid] == item:
            return True
        elif item < li[mid]:
            return serrch_binary_recursion(li[:mid], item)
        else:
            return serrch_binary_recursion(li[mid + 1:], item)
    return False


if __name__ == "__main__":

    l = [1, 3, 6, 8, 9, 15, 18, 20, 30]
    result = search_binary_not_recursion(l, 20)
    print(result)

    result = serrch_binary_recursion(l, 19)
    print(result)