二分法查找的两种方法

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。

#非递归实现二分查找
def binary_search(array, target):
    left = 0
    right = len(array)-1
    while left <= right:
        mid = (left+right)//2
        if array[mid] == target:
            return True
        elif target < array[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

False
True
#递归二分查找
def binary_search(array, target):
    n = len(array)
    if n>0:
        mid = n // 2
        if array[mid] == target:
            return True
        elif array[mid] < target:
            return binary_search(array[mid+1:], target)
        else:
            return binary_search(array[:mid-1], target)
    return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

False
True

两种方法你学会了吗?

    原文作者:yzhua_777
    原文地址: https://blog.csdn.net/yzhua_777/article/details/106043351
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞