这两天一路超神从青铜升级到了黄金(钟无艳、鲁班全图猥琐偷人,欢迎一起开黑),本着劳逸结合的精神(zhuangbi)看了一会儿技术论坛,胡看乱看时瞄到了二分查找,反正也无聊,就决定动动脑子动动手,用php实现一下。
懂的人就不用看了,本篇纯属扯淡。。。
首先介绍一下神马叫二分查找,为什么要介绍呢?因为我相信看到这片文章的肯定有人不知道,知道也不知道啥原理,知道原理也不知道咋实现,别笑了,说的就是你!
嗯。。。 还是自己百度吧,懒得解释名词。
别打我,说一下思路才是关键:
首先,二分查找法需要数组是一个有序的数组。
一、要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比。
二、如果中间位置的值等于我们的给定值,那恭喜你人品蛮好的。
二。如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值。
三。反之,如果中间值小于我们给定的值,那么说明给定值在中间位置之后,此时需要再次将后一部分的值进行二分,因为在中间值之后,所以我们需要改变的值是开始位置的值。
思路很简单,下面贴代码:
erfen.php
先别急着吐槽我的命名,也不要急着夸我代码写的漂亮,先看下执行结果:
是不是666?好开心呀˜˜ 然后我又试了一下1,也顺利的打印了结果,内心更加澎湃了,再试试10。
开心了喝了口水回来一看,纳尼?死循环了?!赶紧杀掉
接下来就是我纠结的心路历程了,这也是为什么我决定写这篇文章的原因(脑子锈脱完后可以嘲讽一下自己)。
起初分析原因时以为是向上取整和向下取整的问题,马上把floor改成ceil,试了一下果然好了,然后试了一下查找1结果1死循环了,瞬间纠结到取整向上还是向下上。在小本本上算了半天。
后来经过反复实验和思考才发现,问题出在最核心的点上,二分查找是找到数组中间的值与值进行对比,我在实现过程中混淆了平常使用排序算法时的思路,忘记了已经对比过的值是不需要再放到等待对比的队列中去的,比如array(0,1),第一次取到的不论向上还是向下,肯定是0或者1,如果对比完我还用这个值作为start或者end,那肯定会陷入死循环中(可向上移步看最初代码)。
下面贴上修改后的代码:
一个简单的算法,因为一时疏忽出了错误,也引发出一个小小的思考,以后写的代码一定要好好测试一下,如果刚刚错误的代码跑到线上,那又是一个给系统埋下炸弹的死循环,切记切记,好好测试(本篇核心价值观)。