C语言:二分法查找

  • Post author:
  • Post category:其他


什么是二分法查找?

二分法查找是通过循环平分的方式,来进行查找想要的数或数据。

那么,要怎么编写这样的代码呢?

首先,要把一系列的数组存入变量当中去,将其当成已知数据。比如将1~10十个数字存到变量中去,就可以写成:

然后就要知道,查找数据是通过下标实现查找的。

这个时候就可以定义变量,通过控制变量进而控制下标的变换,就比如可以这样定义:

因为存入的是十个数字,第一个数字的下标是1,第十个数字的下标正好是9,所以定义left = 0;right = 9 。

然后就是二分法来缩小范围,先收尾相加除以2定义为中间变量,例如:

再通过看中间变量和输入数字的位置关系,确定中间变量是要赋值给 left 还是赋值给 right 。这个时候就可以使用 if 语句进行判定了。

同时,要记得,如果赋值给 left 的话,应该加1再赋值到left,因为刚才已经判定了中间变量与输入数字的位置关系,可以确定输入数字是不包括中间变量的,因此中间变量加1在不违反所要结果的同时,进一步缩小了范围,提高了代码运行速率。

同理可得,如果赋值给right的话,应该减1再赋值到right。

例如:

最后,就是将代码合并起来,所以,二分法找下标的完整代码:

对此,还可以对这个代码进一步推广,比如,可以用循环将数字个数存入数组中,这样存入的数字就不限于10个数字,推广到可以存入尽可能多的数字;找下标也可以推广到通过这个下标进而在这个数组中找到其中的数字。

但是,这样推广后就会存在一个问题:right 是要知道数组中最后一个数字的下标,才能够进行的,如果推广到数组中有很多个数字,以至于在短时间内很难去确定其下标,那 right 又应该如何赋值呢?

如上图所示,可以将数组的总长度除以每个数字的长度,就可以知道总共有多少个数字。然后就可以赋值给 right 。

注意在赋值给 right 的时候,需要先减1再赋值,因为数字总比下标大1。

这样,就可以完成二分法查找的整个过程了。



版权声明:本文为Faith_cxz原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。