查找算法之顺序查找

参考：

1. 顺序查找 | 博客园

基本思想：

顺序查找，就是从第一个元素开始，按索引顺序遍历待查找序列，直到找出给定目标或者查找失败。

特点：

1. 对待查序列（表）无要求 -- 待查找序列可以是有序，也可以是无序；

2. 从第一个元素开始；

3. 需要逐一遍历整个待查序列（除非已经找到）；

4. 若查找到最后一个元素还没找到，则查找失败；

缺点：

效率低 -- 需要遍历整个待查序列

时间复杂度：

O(n)，平均查找时间 = 列表长度/2

空间复杂度：

1个待查序列+1个目标元素 <=> O(n)

看一组示例，从一组数据[3,6,7,2,12,9,0,11]中查找12，

初始状态：指针p指向列表第一个元素，即索引为0元素，开始向右滑动，以匹配、查找目标

查找算法之顺序查找

Step1：p指针开始向右滑行一个单位，进行比较

查找算法之顺序查找

Step2，3，直到4：查找到元素12，匹配目标12成功，索引=4

查找算法之顺序查找

示例代码

data = [3,6,7,2,12,9,0,11]


"""
sequence search 
"""
def seqsearch(array, target):
    i = 0
    for i in range(len(array)):
        element = array[i]
        if element == target:
            print 'sucess to find out %d from array, index=%d'%(target, i)
            return i

    print 'fail to find out the target'
    return -1


print seqsearch(data, 12) #sucess to find out
print seqsearch(data, 8) #fail to find out

运行结果

sucess to find out 12 from array, index=4
4
fail to find out the target
-1

原文链接: https://www.cnblogs.com/fortunely/p/9616597.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/403262

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

查找算法之顺序查找

相关推荐