各位小伙伴大家好;
本期我们要学习的是考试中经常出现或者说是必考的内容——二分法查找。
所谓二分法查找就是逐一将目标元素和中间元素相比较。
如果目标元素比数组的中间元素大则继续将后半部分的中间元素。
如果目标元素比中间元素小,则继续和前半部分的中间比较。
一直重复上述过程直到,找到目标元素,或则条件满足跳出循环。
来看一个实例:
上面的程序中我们实现声明了一个数组,同时声明了三个整型变量。
变量x用来保存目标元素,变量low用来保存比较数组的开始位置,变量high用来保存比较数组的结束位置。
在while循环中,声明了一个局部变量mid中来保存中间元素的位置。
接下来就是一个if判断语句,如果目标元素和中间元素到得相等,则输出该元素。
如果不相等,再继续判断是大于还是小于中间元素。
如果是大于中间元素,则说明目标元素在当前数组的后半部分。
处理的方式是将开始变量low指向中间位置的后一个位置。
如果是目标元素小于中间元素,则说明目标元素在当前数组的前半部分。
处理的方法是将结束变量high指向中间位置的前一个位置。
对于上面这段话,初学可能还需要自己到本子上画一画,才能彻底理解。
下面是一个查找元素24的执行过程示意图,希望能加深大家的理解。
上面的程序其实还是有些不甚完善的地方,下面我们使用函数的方式再来完成一遍。
这里我们一开始就声明和定义了一个函数bise,它接受一个参数作为目标元素。
我们将整个比对过程都写到函数里面,达到一定的封装效果。
如果比对成功我们的函数则将目标元素的位置作为返回值,如果目标元素不存在则返回-1.
这样我们就可以通过函数到的返回值来判断目标元素是否存在,如果不存在则输出提示,
如果存在则输出位置。
函数的说明都写在程序的注释中,就不一一解释了。
如果有什么不懂得或者你有更好的解决方法,相信你一定能从文中找到我的联系方式,欢迎你和我交流。
LIVE
历
史
文
章
友情推荐
领取专属 10元无门槛券
私享最新 技术干货