本文主要是介绍一起talk C栗子吧(第二十五回:C语言实例--二分查找),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
各位看官们,大家好,上一回中咱们说的是顺序查找的例子,这一回咱们说的例子是:二分查找。闲话休
提,言归正转。让我们一起talk C栗子吧!
看官们,我们在上一回中说了查找的相关内容,并且介绍了一种查找方法:顺序查找。大家还记得吗?台
下有看官说:记得呢。我刚想表扬一下这位看官,但是话还没有出口,这看官就又说了:就是不知道哪个
人最后找到钥匙没有。。。我什么表扬的话也没有说,大声吆喝道:“这一回中,我给大家介绍一种新的查
找方法:二分查找法。或者叫折半查找法也可以。”
在介绍二分查找法之前,我们还遵守上一回中约定的前提条件:查找的范围限定为某些容器,这些容器就
是我们前面说过的链表,栈,队列 。查找的内容就是这些容器中的某个元素。二分查找法就是先确定查找
内容在容器中的查找区间,然后逐步缩小查找区间,直到区间中为空(也就是区间中没有元素)。在查找
过程中比较查找的内容与容器中的元素,如果查找的内容与容器中的某个元素相同,那么表示已经从容器
中查找到想要的内容了。我们可以称其为:查找成功。如果查找的内容与容器中的所有元素都不相同,那
么表示容器中没有我们想要查找的内容。我们可以称其为:查找失败。
在使用二分查找法之前,我们需要确保容器中的元素是有序的,比如容器中的元素按照从小到大的顺序存
放。只有确保容器中的元素有序,才能确定查找区间。接下来我们说说二分查找法的实现步骤。
1.首先确定查找区间。第一次查找时把整个容器定义为查找区间。第一次以后查找时查找区间会变化;
2.拿出位于容器中间的元素,让它与我们想要查找的内容进行比较。如果二者相等,那么查找成功。
这时可以停止查找了。如果二者不相等,那么进入下一步;
3.如果容器中间的元素比我们想要查找的内容大,那么把容器中间到容器结尾这部分区间定为新的查
找区间。然后回到步骤1中,继续进行查找;
4.如果容器中间的元素比我们想要查找的内容小,那么把容器开始到容器中间这部分区间定为新的查
找区间。然后回到步骤1中,继续进行查找;
5.重复步骤1到步骤4,直到查找的区间变空时停止查找;
6.确定停止查找的原因 .如果是在步骤2中停止的查找,那么我们可以说查找成功。如果是在步骤5中
停止的查找,那么我们可以说查找失败。
大家可以看到,在查找过程中,没有划分为查找区间中的容器空间,我们不再需要去这些空间中查找,这
样可以节省查找时间。而且整个查找过程中,我们在不断地缩小查找区间,因此节省的时间是相当可以观
的,当容器很大时,更能体现出来。
二分查找法与我们前一回说的顺序查找法相比较而言,效率要高。因此在程序中经常使用该方法去查找需
要的内容。当然了,如果查找的容器比较小,使用二分查找法时,还需要给容器中的元素进行排序,这也
需要消耗时间的,排序时间再加上二分查找时间估计比顺序查找的时间还有长一些。所以在小容器中查找
内容时,使用简单的顺序查找方法就可以了,正所谓杀鸡焉用牛刀。如果查找的窗口比较大,那么最好还
是使用二分查找法,不然使用顺序查找那把”小刀“,不知道猴年马月才能杀掉一头”大牛“。
看官们,正文中就不写代码了,详细的代码放到了我的资源中,大家可以点击这里下载使用。
看官们,其实我们在日常生也使用过二分查找法,只是没有太在意而已。为了大家理解容易,我们举个日
常生活中的例子,该例子还是上一回结尾时的例子:小明回家时需要使用钥匙开门,这时就去衣服口袋里
找,这便是在确定查找区间。小明穿的是T恤,没有口袋,所以他就去裤子的口袋里找,这便缩小查找区
间,同时也指定了新的查找区间;裤子上的口袋都找遍了,还是没有找到钥匙。我的钥匙去哪儿了?这还
用问,肯定是丢了呀。哈哈!
各位看官,关于二分查找的例子咱们就说到这里。欲知后面还有什么例子,且听下回分解。
这篇关于一起talk C栗子吧(第二十五回:C语言实例--二分查找)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!