2011年计算机二级公共基础知识辅导笔记（7）

文章作者 100test 发表时间 2011:03:18 18:47:46
来源 100Test.Com百考试题网

　　1.7 查找

　　1.7.1 顺序查找

　　查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。

　　例如，在一维数组[21，46，24，99，57，77，86]中，查找数据元素99，首

　　先从第1个元素21开始进行比较，比较结果与要查找的数据不相等，接着与第2个元素46进行比较，以此类推，当进行到与第4个元素比较时，它们相等，所以查找成功。如果查找数据元素100，则整个线性表扫描完毕，仍未找到与100相等的元素，表示线性表中没有要查找的元素。

　　在下列两种情况下也只能采用顺序查找：

　　①如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找；

　　②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。

　　1.7.2 二分法查找

　　二分法查找，也称拆半查找，是一种高效的查找方法。能使用二分法查找的线性表必须满足用顺序存储结构和线性表是有序表两个条件。

　　“有序”是特指元素按非递减排列，即从小到大排列，但允许相邻元素相等。下一节排序中，有序的含义也是如此。

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

　　步骤1：将X与线性表的中间项比较；

　　步骤2：如果X的值与中间项的值相等，则查找成功，结束查找；

　　步骤3：如果X小于中间项的值，则在线性表的前半部分以二分法继续查找；

　　步骤4：如果X大于中间项的值，则在线性表的后半部分以二分法继续查找。

　　例如，长度为8的线性表关键码序列为：[6，13，27，30，38，46，47，70]，被查元素为38，首先将与线性表的中间项比较，即与第4个数据元素30相比较，38大于中间项30的值，则在线性表[38，46，47，70]中继续查找；接着与中间项比较，即与第2个元素46相比较，38小于46，则在线性表[38]中继续查找，最后一次比较相等，查找成功。

　　顺序查找法每一次比较，只将查找范围减少1，而二分法查找，每比较一次，可将查找范围减少为原来的一半，效率大大提高。

　　对于长度为n的有序线性表，在最坏情况下，二分法查找只需比较log2n次，

　　而顺序查找需要比较n次。

　　#ff0000>