Python3查找算法02 - 二分查找

  • 原创
  • Madman
  • /
  • /
  • 0
  • 1731 次阅读

Synopsis: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表

代码已上传到 https://github.com/wangy8961/python3-algorithms ,欢迎star

1. 二分查找

二分查找(binary search),也称折半查找(half-interval search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程为,从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果要查找的元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半

2. 非递归实现

def binary_search(L, item):
    '''非递归实现二分查找,输入的列表必须是有序的(比如,从小到大排列)'''
    first = 0
    last = len(L) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last) // 2
        print('first = {}, last = {}, midpoint = {}'.format(first, last, midpoint))  # 测试
        if L[midpoint] == item:  # 找到了
            found = True
        else:
            if item 
                                
                            
未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3查找算法02 - 二分查找

分享

作者

作者头像

Madman

如需 Linux / Python 相关问题付费解答,请按如下方式联系我

0 条评论

暂时还没有评论.