考点7 查找技术

1.顺序查找

顺序查找一般是指在线性表中查找指定的元素。其基本思路是：从表中的第一个元素开始，依次将线性表中的元素与被查找元素进行比较，直到两者相符，查到所要找的元素为止。否则，表中没有要找的元素，查找不成功。

在最好的情况下，第一个元素就是要查找的元素，则比较次数为1次。

在最坏的情况下，顺序查找需要比较n次。

在平均情况下，需要比较n／2次。因此查找算法的时间复杂度为O（n）。

在下列两种情况下只能够采取顺序查找：

●如果线性表中元素的排列是无序的，则无论是顺序存储结构还是链式存储结构，都只能用顺序查找；

真考链接

考核概率为35%，考生需要理解该考点内容，主要是顺序查找与二分查找的概念，以及一些查找的方法。

●即便是有序线性表，若采用链式存储结构，只能进行顺序查找。

2.二分查找

使用二分法查找的线性表必须满足以下两个条件：

●顺序存储结构；

●线性表是有序表。

所谓有序表，是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。

对于长度为n的有序线性表，利用二分法查找元素x的过程如下。

（1）将x与线性表的中间项进行比较。

（2）若中间项的值等于x，则查找成功，结束查找。

（3）若x小于中间项的值，则在线性表的前半部分以二分法继续查找。

（4）若x大于中间项的值，则在线性表的后半部分以二分法继续查找。

这样反复进行查找，直到查找成功或子表长度为0（说明线性表中没有这个元素）为止。

当有序线性表为顺序存储时采用二分查找的效率要比顺序查找高得多。对于长度为n的有序线性表，在最坏的情况下，二分查找只需比较log2n次，而顺序查找则需要比较n次。

真题精选

下列数据结构中，能用二分法进行查找的是______。

A）顺序存储的有序线性表

B）线性链表

C）二叉链表

D）有序线性链表

【答案】A

【解析】二分法查找只适用于顺序存储的有序表。所谓有序表是指线性表中的元素按值非递减排列（即从小到大，但允许相邻元素值相等）。