Python3查找算法01 - 顺序查找

  • 原创
  • Madman
  • /
  • 2018-09-09 15:21
  • /
  • 0
  • 194 次阅读

Synopsis: 先介绍一种最低效的查找算法,顺序查找,它适合于存储结构为顺序存储或链接存储的线性表。无序查找是被查找数列有序无序均可,有序查找是被查找数列必须为有序数列。输入的数列如果是有序的,我们可以稍微改进一下这个算法的效率

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

1. 顺序查找

顺序查找(Sequential Search)也称为线性查找,它从线性表的一端开始,顺序扫描,依次将扫描到的元素值与查找值比较,如果相等则表示查找成功,直接返回True;如果不等则继续往后遍历,当遍历完整个线性表还没有找到,则表示查找失败,返回False

2. 查找无序数列

def sequential_search(L, item):
    '''顺序查找,输入的列表是无序的'''
    pos = 0
    found = False  # 标记是否已找到数据项

    while pos < len(L) and not found:
        if L[pos] == item:  # 表示找到了
            found = True
        else:
            pos += 1

    return found


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

性能分析:

情形 最优时间复杂度 最坏时间复杂度 平均时间复杂度
item 在线性表中 O(1) O(n) O(n/2)
item 不在线性表中 O(n) O(n) O(n)

我们发现,如果要查找的数据项不在给定的线性表中时,时间复杂度永远是O(n),因为都需要遍历到线性表的末尾

3. 查找有序数列

现实中,可能给定的线性表是已排好序的(比如,按从小到大),那么,我们可以改进一下算法,当遍历到某个元素时,它比要查找的数据项大,则说明后续的元素肯定都比要查找的数据项大,就可以在这个位置停止查找了,因为它肯定不在线性表中

def sequential_search(L, item):
    '''顺序查找,输入的列表是有序的(从小到大排列)'''
    pos = 0
    found = False  # 标记是否已找到数据项
    stop = False  # 如果遍历到的元素值比 item 大,则说明不用再继续了(因为后续的元素肯定都比 item 大)

    while pos < len(L) and not found and not stop:
        # print(pos)  # 测试
        if L[pos] == item:  # 表示找到了
            found = True
        else:
            if L[pos] > item:
                stop = True
            else:
                pos += 1

    return found


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

性能分析:

情形 最优时间复杂度 最坏时间复杂度 平均时间复杂度
item 在线性表中 O(1) O(n) O(n/2)
item 不在线性表中 O(1) O(n) O(n/2)

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

未经允许不得转载: LIFE & SHARE - 王颜公子 » Python3查找算法01 - 顺序查找

分享

作者

作者头像

Madman

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

0 条评论

暂时还没有评论.

发表评论前请先登录