這篇文章主要介紹了php二分查找的二種實現示例，遞歸解法二分查找和非遞歸算法二分查找的示例,需要的朋友可以參考下
php二分查找示例 二分查找常用寫法有遞歸和非遞歸，在尋找中值的時候，可以用插值法代替求中值法。 當有序數組中的數據均勻遞增時，采用插值方法可以將算法復雜度從中值法的lgN減小到lglgN 代碼如下: /** * 二分查找遞歸解法 * @param type $subject * @param type $start * @param type $end * @param type $key * @return boolean */ function binarySearch_r($subject, $start, $end, $key) { if ( $start >= $end ) return FALSE; $mid = getMidKey($subject, $start, $end, $key); if ( $subject[$mid] == $key ) return $mid; if ( $key > $subject[$mid] ) { return binarySearch($subject, $mid, $end, $key); } if ( $key <= $subject[$mid] ) { return binarySearch($subject, $start, $mid, $key); } } /** * 二分查找的非遞歸算法 * @param type $subject * @param type $n * @param type $key */ function binarySearch_nr($subject, $n, $key) { $low = 0; $high = $n; while ( $low <= $high ) { $mid = getMidKey($subject, $low, $high, $key); if ( $subject[$mid] == $key ) return $mid; if ( $subject[$mid] < $key ) { $low = $mid + 1; } if ( $subject[$mid] > $key ) { $high = $mid - 1; } } } function getMidKey($subject, $low, $high, $key) { /** * 取中值算法1 取中值 不用 ($low+$high)/2的方式是因為 防止low和high較大時候，產生溢出.... */ //return round($low + ($high - $low) / 2); /** * 經過改進的插值算法求中值，當數值分布均勻情況下，再降低算法復雜度到lglgN * 取中值算法2 */ return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) ); }
