Python3查找算法02 - 二分查找

  • 原创
  • Madman
  • /
  • 2018-09-10 15:51
  • /
  • 1
  • 108 次阅读

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 < L[midpoint]:  # 说明 item 在左半部分
                last = midpoint - 1
            else:  # 说明 item 在右半部分
                first = midpoint + 1

    return found


if __name__ == '__main__':
    L1 = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    item = 31
    # item = 32  # 测试
    print('{} 是否在列表中: {}'.format(item, binary_search(L1, item)))

3. 递归实现

def binary_search(L, item):
    '''递归实现二分查找,输入的列表必须是有序的(比如,从小到大排列)'''
    if len(L) == 0:
        return False
    else:
        midpoint = len(L) // 2
        print('midpoint = {}'.format(midpoint))  # 测试
        if L[midpoint] == item:  # 找到了
            return True
        else:
            if item < L[midpoint]:  # 说明 item 在左半部分
                return binary_search(L[:midpoint], item)
            else:  # 说明 item 在右半部分
                return binary_search(L[midpoint+1:], item)


if __name__ == '__main__':
    L1 = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    item = 31
    # item = 32  # 测试
    print('{} 是否在列表中: {}'.format(item, binary_search(L1, item)))

4. 性能分析

比较次数 剩余元素的数目
1 n/2
2 n/4
3 n/8
...
i n/2i

所以,二分查找的最优时间复杂度为O(1),最坏时间复杂度为O(log n)

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3查找算法02 - 二分查找

分享

作者

作者头像

Madman

如果博文内容有误或其它任何问题,欢迎留言评论,我会尽快回复; 或者通过QQ、微信等联系我

1 条评论

匿名头像
test
2018-10-18 17:35

test

发表评论前请先登录