二分法算法实现

二分查找(binary search)，也叫做折半查找。主要是对一个已经排序的数组进行查找，复杂度为O(logn)。

基本过程：

将要查找的值x与数组的中间元素进行比较。如果输入的值x 小于中间元素的值，则在该数组的前半部分查找;否则，在该数组的后半部分查找。如此循环，直到得出结果。

//php的二分法搜索
function binarysearch($key,$arr) {
$low =  0;
$high = count($arr) -1 ;

while($low <=  $high)
{
$mid = (int)(($low + $high)/2);
if ($key < $arr[$mid]) $high = $mid -1; else if ($key > $arr[$mid])
$low = $mid + 1;
else
return $mid;
}
return -1;
}

//测试
$test = array(1,2,3,5,7,9,11,20,222);
$key = 20;
$result = binarysearch($key,$test);
//返回的是7
echo $result;