> 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。其实，二分查找也还是比较容易理解的，大概就是一分为二，然后两边比较，保留有效区间，继续一分为二查找，直到找到或者超出区间则结束。 **满足该算法的要求必须如下两点**： 1、必须采用顺序存储结构。 2、必须按关键字大小有序排列。 **算法步骤**： 1、确定要查找的区间 2、确定要二分时的参照点 3、区间内选取二分点 4、根据二分点的值，综合左右区间情况以及求解的目的，舍去一半无用的区间 5、 继续在有效区间重复上面的步骤 ``` /** * 二分查找算法 * 第一种实现方式：循环方式 * @param int $number * @param array $arr * @return int */ function binary_search($number,$arr){ if(!in_array($number,$arr) || empty($number)){ return -1; } $length = count($arr); $lower = 0; $higher = $length-1; while ($lower <= $higher){ $middle = intval(($lower + $higher)/2); if($arr[$middle] > $number){ // 以中间点作为参照点比较，查找数比参照点小，舍去右边，否则舍弃左边区间 $higher = $middle - 1; }elseif ($arr[$middle] < $number){ $lower = $middle +1; }else{ return $middle; } } return -1; } // 待查找区间 $arr = [1, 3, 7, 9, 11, 57, 63, 99]; // 非递归查找57所在的位置 $find_key = binary_search($arr, 57); print_r($find_key); ``` ``` /** * 二分查找算法 * 第二种实现方式：递归 * @param array $arr * @param int $number * @param int $lower * @param int $higher * @return int */ function binary_search_recursion($arr,$number,$lower,$higher){ if($lower > $higher){ return -1; } $middle = intval(($lower+$higher) /2); if($number > $arr[$middle]){ // 查找数比参照点大，舍去左边继续查找 return binary_search_recursion($arr,$number,$middle+1,$higher); }elseif ($number < $arr[$middle]){ return binary_search_recursion($arr,$number,$lower,$middle-1); }else{ return $middle; } } $arr = [1, 3, 7, 9, 11, 57, 63, 99]; $key = binary_search_recursion($arr,11,0,count($arr)); print_r($key);die; ```