二分查找，往往是针对有序的数组进行查找，我们假设一个序列是数组有序，然后给定一个数字，查出它应该在这个数组中的排序位置
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列
折半查找这个名字一听，你就知道是怎么回事了。
我们举个例子看看
1 3 5 7 9 10 是已经排好序的数组，如果现在要求查X，我们如何查出X放在哪个位置呢？
很显然，我们可以取最中间的那个，然后假如找不到，就看中间的那个是大于X还是小于X 如果小于X，说明X应该在后半部分，如果是大于X，则说明在前半部分，那么此时，再以当前中间节点为起始或者终止节点组成新数组，再次查找，如此往返，总能找到X的位置。
还是直接看代码吧，最简单的方式，递归实现，代码如下：
<?php
function 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循环实现迭代的方式来实现，代码如下：
<?php
function 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);
截图如下：
这样的话，循环次数也少了，改写了递归，降低了计算的复杂度。
