当前位置： 移动技术网 > IT编程>脚本编程>Python > python 数据结构之二分查找的递归和普通实现

python 数据结构之二分查找的递归和普通实现

2018年10月08日  | 移动技术网IT编程  | 我要评论

昆山视窗人才网,刘丛丹多大,云南经济管理职业学院

二分查找就是待查找的列表进行分半搜索

如下所示

二分查找普通实现：

def erfen(alist, item):
    start = 0
    end = len(alist) - 1
    while start <= end:
        n = int((start + end) / 2)
        if alist[n] == item:
            return true
        elif alist[n] > item:
            end = n - 1
        else:
            start = n + 1
    return false


alist = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(erfen(alist,10))
print(erfen(alist, 3))

递归实现：

#import sys
#sys.setrecursionlimit(1000000)
"""解决maximum recursion depth exceeded error """

def erfen(alist,item):
    if len(alist) == 0:
        return false
    else:
        mid=int(len(alist)/2)
        if alist[mid] == item :
            return true
        elif item < alist[mid]:
            return erfen(alist[:mid],item)
        else :
            return erfen(alist[mid+1:],item)

alist = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(erfen(alist,10))
print(erfen(alist, 3))

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网