二分查找法

<?php
/**
 * @param array $arr    递增数字数组
 * @param int   $number 待查找的数字
 * @return int          返回找到的键
 */
function binary_search($arr,$number){
    // 非数组或数组为空，返回-1
    if(!is_array($arr)||empty($arr)){
        return -1;
    }
    // 初始化变量值
    $len = count($arr);
    $lower = 0;
    $high = $len - 1;
    // 最低点比最高点大就退出
    while($lower<=$high){
        //以中间点作为参照点
        $middle = intval(($lower+$high)/2);

        if($number < $arr[$middle]){
            $high = $middle - 1;  // 查找数比参照点小，则舍去右边
        }else if ($number > $arr[$middle]){
            $lower = $middle + 1; // 查找数比参照点大，则舍去左  边
        }else{
            return $middle;
        }
    }
    //未找到，返回-1
    return -1;
}
$arr = [1,3,5,7,9,11,16,26,27,29,34,35,39,65,97];
$find_key = binary_search($arr,27);
echo ‘$arr[‘.$find_key.‘]=‘.$arr[$find_key];

在有序数组中如果用暴力算法查找，也就是阻隔遍历比较，那么时间复杂度是O（n）；

但是用二分法查找，每次都会舍弃一般查找区间，所以复杂度是O（logn）；