C语言——折半查找法

一、使用场景

假如现在有一组数据,你想要查询这个具体某一个数据在这一堆数据中的所在位置,这个时候就需要程序在这一组数据中,找到与想要查找的目标数据相匹配的那个数据,然后返回相对应的位置。如果将问题再细化简化一点,假如现在有一组有顺序的数字,需要你编写程序找到其中一个数字所在的位置。了解需求之后,我们脑海中一般首先浮现的思路便是,编写一个数组,然后将数字一个个进行匹配,最后找到这个数字的位置,返回该位置,问题解决。

现在我们就将此思路实践一下看看是否能够找到该数字。给出一个包含十个元素的数组,里面包含了1,2,3,4,5,6,7,8,9,10,然后尝试在其中找到数字7对应的位置,代码如下所示:

上面的代码使用了flag作为一个标志数,因为成功找到后break跳出循环继续执行,但是如果查找的是一个不存在该数组中的数字时,对上面数据全部进行查找之后也会结束循环执行,此时如果没有标志数,程序就无法判断是因为哪种原因跳出了循环结构。所以定义一个变量flag进行判断:如果成功找到,flag的值为1,否则为0,程序就能通过if语句进行判断是哪种情况,判断是否输出找不到情况下的语句。

我们发现最后是可以实现这个目标的,成功找到了数字7在这个数字中对应的位置:7.(这个位置是指在数字的位置而不是数组中的下标)。

但是这样一个个数字进行匹配,虽然能找到对应位置,但是假如现在有100或者1000甚至10000个数字,然后想要找到比较靠后的一个数字对应的位置时,这种方法就显得有些许“笨拙”了,不够灵活和简便,要将所有数字从头到尾一个个进行匹配,直至找到为止。此时就需要使用一个更加简便更加快速的方法——折半查找法,或者叫做二分查找法。

二、如何实现折半查找法

假如一天你的同学买了一双球鞋,只告诉你这双鞋在一千以内,然后让你猜这双鞋价格是多少,你会怎么做?可能有少部分人会上来就给这位朋友一拳,然后一顿输出“你买鞋又不是买给我,还**让我猜价钱,凡尔赛你**,我******”,但是大多数人还是会选择正确的做法:从中间数500开始猜,而不是像上面的做法一样,真的就傻傻的从1,2,3开始猜到1000。所以折半查找法的思想也是如此。

我们从这一组有序数字中,取其中位数与我们查找的目标数进行匹配,如果正好一发入魂,那就直接找到了该数,但是即使大概率不正确,我们也可以直接干掉一半的数据。举个例子:假如现在有个数组是1-1000,目标数是777,那么我中位数是500,进行比较之后是比目标数更小,那就说明目标数的位置只可能在中位数往上,而不能在500之下,那么500以下的数字就全部被干倒了,这一次查找就可以消灭掉一半数据,而上面的做法一次只能消灭一个数字,效率相比之下就产生了很明显的差距了。然后第一次查找后再进行第二次折半,取750进行比较,这次还是比目标数小,但是仍然干掉了一半数据,依次进行下去,只需使用少数次数查找便可以从大量数据中找到。

现在还是使用上面的例子,示例以下折半查找法:

 上面代码中先定义了一个左下标和右下标,从而定义出中位数的下标。每次查找之后,如果目标数 > 中位数,那么目标数只会出现在中位数往上的位置,那么此时右下标不需变动,左下标应该是中位数的下标 +1,再次对左右下标相加除以2,取得剩下数据的中位数作为新的中位数进行下一次查找。如果目标数 < 中位数,那么目标数只会出现在中位数之下的位置,那么此时左下标不需变动,右下标应该是中位数的下标 -1,然后再次取新的中位数,以此类推进行查找,所以使用while循环。

第一次查找的图示如下,第一次查找之后可知 k > 中位数,所以 k 的位置只可能出现在中位数的右边,此时我们的第二次查找想要从中位数的右边第一个数开始找起,所以此时左下标应该是 mid + 1。

 所以第二次查找如下,可知现在 k < 中位数,所以只可能出现在中位数的左边,此时我们希望下次查找从中位数的左边第一个数开始,所以此时右下标为 mid - 1。

 然后后续查找都如上图所示,直至左右下标交错(left > right)或者相等(left = right),便是循环结束的标志。

 

 三、总结

折半查找法每一次查找都可以判断一半数量的数据是否匹配,效率比第一种方法高效很多。k = 7 这种情况是查找次数最多的情况,都只需要四次查找即可完成,但是第一种方法查找需要七次,相比之下,足以见得折半查找法的高效性。

但是折半查找法也是需要前提条件才可以使用的,就是要求查找的这组数据必须是有序的,倒序和顺序都可以。面对无序的数据,折半查找法就失效,这也是相较于第一种方法的不足之处,两种方法各有所长,须根据不同情况进行使用。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>