计算机二级公基知识7-查找

顺序查找与二分查找。本部分内容对OIer同样适用。


先来说个我之前听到的笑话:

这个笑话其实就是讲的顺序查找与二分查找。大妈以为这里面只有一本书没有过安检,所以采用了二分查找来提高效率,但实际上这些书都没有过安检233333

查找算法是一种非常重要的算法。查找的效率直接关系着数据处理的效率。顾名思义,查找算法就是在一个给定的数据结构中寻找指定的元素。通常的,根据数据结构的不同,所使用的查找算法也不同。这里重点讨论顺序查找与二分查找。

顺序查找

顺序查找一般用于线性表。它的思路很简单,挨个比对。从线性表的第一个元素开始,依次比对需要查找的元素。如果发现线性表中的某个元素与需要查找的元素相符,则说明查找成功。如果查遍了整个线性表都没有找到那就是查找失败。

顺序查找所需要的时间取决于查找元素相对于第一个元素的距离。在最坏情况下,需要对整个线性表做比较才能找到。平均的,利用顺序查找法在线性表中查找一个元素,大约要与线性表中的一半的元素进行比较。

也就是说,在线性表比较大的情况下,使用顺序查找的效率是比较低的。但是有两种情况,这两种情况下只能使用顺序查找。

  1. 线性表无序。这种情况下只能使用顺序查找,因为下面要介绍的二分查找是需要元素有序的(笑话所提到的那种情况比较特殊,那个不能用顺序和无序来解释)。
  2. 如果采用链式存储结构,则只能使用顺序查找。

二分查找

二分查找只适用于顺序存储的线性有序表。它要求元素必须要递增或者递减排列。

其实二分查找是一个递归的过程。对于整个元素区间,我们知道它是有序的,那么我们就取一下整个区间的中间元素,比对一下是不是要找的元素。如果不是,就要判断大小。这里我们以元素从左到右升序排列举例。

如果要查找的值比中值小,那说明中值是比较大的,那说明要查找的值是在区间的左半边的。然后我们以中值作为最大值,最小值还是原来那个,递归地查找这个元素。递归的边界是左右区间重合。如果最后查到区间长度就剩1,这个最后的元素也不是我们想要的,那只能说明线性表中没有我们要查找的元素。

虽然应用二分查找需要一定条件,但是二分查找的效率要比顺序查找高得多。这就正如笑话中提到的那两个时间复杂度。顺序查找的时间复杂度是O(n),但是二分查找的时间复杂度就是O(log2n)。


-------------本文结束,感谢您的阅读转载请注明原作者及出处-------------


本文标题:计算机二级公基知识7-查找

文章作者:Shawn Zhou

发布时间:2018年08月13日 - 17:08

最后更新:2018年12月09日 - 18:12

原始链接:http://yoursite.com/2018/08/13/国考计算机二级公共基础知识-Part-7/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

知识无价,码字不易。对您有用,敬请打赏。金额随意,感谢关心。