顺序查找Sequential Search

无序表查找

如果数据项保存在如列表这样的集合中，我们会称这些数据项具有线性或者顺序关系。 在Python List中,这些数据项的存储位置称为下标( index) ,这些下标都是有序的整数。 通过下标,我们就可以按照顺序来访问和查找数据项,这种技术称为“顺序查找”

要确定列表中是否存在需要查找的数据项

首先从列表的第1个数据项开始, 按照下标增长的顺序，逐个比对数据项,如果到最后一个都未发现要查找的项，那么查找 失败。

代码很简单：

def sequentialSearch(alist, item): pos = 0 found = False while not Found and pos<len(alist): if alist[pos] == item: found = True else: pos += 1 return found

无序表查找算法分析

在查找算法中,这种基本计算步骤就是进行数据项的比对当前数据项等于还是不等于要查找的数据项，比对的次数决定了算法复杂度。

在顺序查找算法中,为了保证是讨论的一般情形,需要假定列表中的数据项并没有按值排列顺序,而是随机放置在列表中的各个位置。换句话说，数据项在列表中各处出现的概率是相同的。

数据项是否在列表中,比对次数是不一样的

如果数据项不在列表中,需要比对所有数据项才能得知,比对次数是n

如果数据项在列表中,要比对的次数,其情况就较为复杂

最好的情况，第1次比对就找到最坏的情况，要n次比对 所以，顺序查找的复杂度是O(n)

有序表查找

当数据项存在时，比对过程与无序表完全相同，不同之处在于，如果数据项不存在，比对可以提前结束

如下图中查找数据项50，当看到54时，可知道后面不可能存在50，可以提前退出查找

代码稍微改动一点：

def sequentialSearch(alist, item): pos = 0 found = False stop = False while not Found and pos<len(alist) and not stop: if alist[pos] == item: found = True else: if alist[pos] > item: stop = True else: pos += 1 return found

有序表查找算法分析

实际上,就算法复杂度而言,仍然是O(n)只是在数据项不存在的时候，有序表的查找能节省一些比对次数,但并不改变其数量级。

二分查找

对于有序表，是否还有更快更好的查找算法

我们从列表中间开始比对。 如果列表中间的项匹配查找项，则查找结束 如果不匹配，那么就有两种情况:

列表中间项比查找项大，那么查找项只可能出现在 前半部分列表中间项比查找项小，那么查找项只可能出现在 后半部分

无论如何，我们都会将比对范围缩小到原来的一半: n/2 继续采用上面的方法查找，每次都会将比对范围缩小一半

def binarySearch(alist, item): first = 0 last = len(alist) - 1 found = False while not found and first <= last: midpoint = (first + last) // 2 if alist[midpoint] == item: found = True else: if alist[midpoint] > item: last = midpoint - 1 else: first = midpoint + 1 return found

二分查找算法实际上体现了解决问题的典型策略:分而治之 将问题分为若干更小规模的部分 通过解决每一个小规模部分问题，并将结果汇总得到原问题的解

显然,递归算法就是一种典型的分治策略算法，二分法也适合用递归算法来实现

def binarySearch(alist, item): # 最小结束条件 if len(alist) == 0: return False else: midpoint = (len(alist)-1) // 2 if alist[midpoint] == item: return True else: if alist[midpoint] > item: return binarySearch(alist[:midpoint], item) else: return binarySearch(alist[midpoint+1:], item)

二分查找算法分析

由于二分查找每次比对都将下一步比对范围缩小一半，每次比对剩余数据项如下表所示。

当比对次数足够多以后,比对范围内就会仅剩余1个数据项 无论这个数据项是否匹配查找项,比对最终都会结束,解下列方程: $$\frac{n}{2^i}=1$$ 得到： $$\mathbf{i}={\log }_2(n)$$ 所以该算法复杂度为 所以二分法查找的算法复杂度是O(log n)

Note：

虽然我们根据比对的次数,得出二分查找的复杂度O(log n) 但本算法中除了比对,还有一个因素需要注意到:

binarySearch(alist[ :midpoint], item) 这个递归调用使用了列表切片，而切片操作的复杂度是O(k)，这样会使整个算法的时间复杂度稍有增加; 当然，我们采用切片是为了程序可读性更好，实际上也可以不切片，而只是传入起始和结束的索引值即可，这样就不会有切片的时间开销了。

进一步思考

另外,虽然二分查找在时间复杂度.上优于顺序查找但也要考虑到对数据项进行排序的开销

如果一次排序后可以进行多次查找，那么排序的开销就可以摊薄

但如果数据集经常变动，查找次数相对较少，那么可能还是直接用无序表加上顺序查找来得经济 所以,在算法选择的问题.上,光看时间复杂度的优劣是不够的,还需要考虑到实际应用的情况。