二分查找，往往是针对有序的数组进行查找，我们假设一个序列是数组有序，然后给定一个数字，查出它应该在这个数组中的排序位置
百度百科中讲到
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
折半查找这个名字一听，你就知道是怎么回事了。
我们举个例子看看
1 3 5 7 9 10 是已经排好序的数组，如果现在要求查X，我们如何查出X放在哪个位置呢？
很显然，我们可以取最中间的那个，然后假如找不到，就看中间的那个是大于X还是小于X 如果小于X，说明X应该在后半部分，如果是大于X，则说明在前半部分，那么此时，再以当前中间节点为起始或者终止节点组成新数组，再次查找，如此往返，总能找到X的位置。
还是直接看代码吧，最简单的方式，递归实现，代码如下：
<?phpfunction binary_search($array,$target,$start,$end){ ???$middle_index = floor(($start+$end)/2); // 定位中间位置的索引 ???$middle_value = $array[$middle_index];//取得中间项的值 ???if($middle_value == $target) ???{ ???????return $middle_index; ???}else if($middle_value >$target) ???{ ???????if($start > $middle_index-1)//如果开始位置都比结束位置大了，表示肯定找不到了 ???????{ ???????????return false; ???????} ???????//中间项比要找的目标大 就去左边找吧 ???????$re = binary_search($array,$target,$start,$middle_index-1); ???}else ???{ ???????if($middle_index+1 > $end)//如果开始位置比结束位置大了 表示肯定找不到了 ???????{ ???????????return false; ???????} ???????//中间项比要找的目标小 就去右边找吧； ???????$re = binary_search($array,$target,$middle_index+1,$end); ???} ???return $re;}$array = array(1,3,5,7,9,10);$search = 9;//要找的数$index = binary_search($array,$search,0,count($array)-1);var_dump($index);截图如下：
我们可以看到，使用递归方式的理解是非常简单的，将大事化小，小事化了，如此往复来解决，分段分块，逐步查找得到改元素，如果找不到 返回false。
那么由于递归一直都是被认为是效率不高的，如何使用其他方式改写一下这样的查找方式呢？
我们可以用while循环实现迭代的方式来实现，代码如下：
<?phpfunction binary_search($array,$target,$start,$end){ ???$middle_index=floor(($start+$end)/2); ???while($start<=$end) ???{ ???????//说明还能继续寻找 ???????if($array[$middle_index]==$target) ???????{ ???????????//找到了 ???????????return $middle_index; ???????}elseif($array[$middle_index]>$target) ???????{ ???????????//说明中间元素大于目标元素 在前半部分 ???????????$end=$middle_index-1;//终止位置从刚刚找到的中间位置的左边那个位置结束 ???????????$middle_index=floor(($start+$end)/2);//重新计算中间位置 ???????}else ???????{ ???????????//说明中间元素小于目标元素 在前半部分 ???????????$start=$middle_index+1;//起始位置中刚刚找到的中间位置的右边那个位置开始 ???????????$middle_index=floor(($start+$end)/2);//重新计算中间位置 ???????} ???} ???return false;//找不到 返回false}$array = array(1,3,5,7,9,10);$search = 9;//要找的数$index = binary_search($array,$search,0,count($array)-1);var_dump($index);截图如下：
这样的话，循环次数也少了，改写了递归，降低了计算的复杂度。
php查找之二分查找
原文地址：https://www.cnblogs.com/lizhaoyao/p/8611143.html