计算机二级公共基础知识总结_2017年计算机二级公共基础知识学习教程：查找技术

　　（七）查找技术

　　查找即是指在一个给定的数据结构中查找某个指定的元素。

　　1．顺序查找

　　顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。

　　基本操作方法是：

　　从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都不相等，则该元素在指定的线性表中不存在。

　　顺序查找的情况：要查找的元素在线性表的第一个元素，则查找效率；如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素，这种情况是最差情况。

　　对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：

　　线性表为无序表，即表中的元素没有排列不是按大小顺序进行排列的，这类线性表不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进行查找

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

　　例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：

　　整个线性表的长度为5

　　查找计次n=1，将元素6与序列的第一个7元素进行比较，不等，继续查找

　　n=2，将6与第二个元素2进行比较，不等，继续

　　n=3，将6与第三个元素1进行比较，不等，继续

　　n=4，将6与第四个元素5进行比较，不等，继续

　　n=5，将6与第五个元素9进行比较，不等，继续

　　n=6，将6与第六个元素4进行比较，不等，继续

　　n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。

　　2．二分查找

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

　　二分查找的方法如下：

　　将要查找的元素与有序序列的中间元素进行比较：

　　如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行查找

　　如果要查找的元素的值比中间元素的值小，则继续在线性表的前半部分（中间项以前的部分）进行查找

　　这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0（说明线性表中没有要查找的元素）

　　有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是log2n次，而顺序查找的最坏情况的查找次数是n次。

　　当然，二分查找的方法也支持顺序存储的递减序列的线性表。

　　有非递减有序线性表：1、2、4、5、7、9，要查找元素6。查找的方法是：

　　序列长度为n=6，中间元素的序号m=[(n+1)/2]=3

　　查找计次k=1，将元素6与中间元素即元素4进行比较，不等，6>4

　　查找计次k=2，查找继续在后半部分进行，后半部分子表的长度为3，计算中间元素的序号：m=3+[(3+1)/2]=5，将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，6<7

　　查找计次k=3，继续查找在后半部分序列的前半部分子序列中查找，子表长度为1，则中间项序号即为m=3+[(1+1)/2]=4，即与第4个元素5进行比较，不相等，继续查找的子表长度为0，则查找结束

本文来源：https://www.wddqw.com/uZUO.html