python 下的数据结构与算法---7:查找

一：线性查找（Sequential Search）

　　线性查找可以说是我们用的最早也会是用的最多的查找方式了。其对应的是线性数据结构，回顾一下线性数据结构，其特点是先后加入的元素是有顺序的，相邻的。而线性结构就是按其顺序挨个遍历的查找方式：

　　for i in range(len(seq)):

　　　　if seq[i] == item:

　　　　　　print('find it in position %d'%i)

　　　　　　break

　　显然，这是O(n)的时间复杂度

二：二分查找（Binary Search）

　　对于已经排好序的元素集，可以使用二分查找，其实也就是数学里面的二分法，每次排除一半的结果

　　def binary_search(a_list, item):

　　　　first = 0

　　　　last = len(a_list) - 1

　　　　found = False

　　　　while first <= last and not found:

　　　　　 midpoint = (first + last) // 2

        if a_list[midpoint] == item:
            found = True
        elif item < a_list[midpoint]:
            last = midpoint - 1
        else:
            first = midpoint + 1
    　　　　 return found
　　test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
　　print(binary_search(test_list, 3))
　　print(binary_search(test_list, 13))

　　显然，时间复杂度为O(logn)

是不是很少，是不是很少，不过problem solving那里面讲search的就只讲了这两个，剩下的search就是在数和图里面讲的针对他们的search了，由于现在总结还没到那儿，所以就不拿过来了，虽然少但是也不能不纪录下来啊。

秒客网

python 下的数据结构与算法---7:查找

相关文章