> 二分查找也稱折半查找（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; ```