本文主要介紹了PHP實現的折半查找演算法,簡單描述了折半查找的原理,並結合實例形式分析了php採用遞歸與非遞歸方式實現折半查找算法的相關操作技巧,需要的朋友可以參考下,希望能幫助大家。
定義:折半查找技術,也就是二分查找。它的前提是線性表中的記錄必須是關鍵碼有序(通常從大到小有序),線性表必須採用順序儲存。
折半查找的基本想法:取中間記錄作為比較對象,若給定值與中間記錄的關鍵字,則在中間記錄的關鍵字相等,則查找成功;若給定值小於中間記錄的作伴去繼續找;若給定值大於中間記錄的關鍵字,則在中間記錄的右半區繼續找。不斷重複上述過程,直到查找成功,或所有查找區域無記錄,查找失敗為止。
實作程式碼:
<?php //递归方式 function bin_recur_search($arr,$val){ global $time; if(count($arr) >= 1){ $mid = intval(count($arr) / 2); $time++; if($arr[$mid] == $val){ return '值为:'.$arr[$mid].'<br>查找次数:'.$time.'<br>'; }elseif($arr[$mid] > $val){ $arr = array_splice($arr,0,$mid); return bin_recur_search($arr, $val); }else{ $arr = array_slice($arr,$mid + 1); return bin_recur_search($arr, $val); } } return '未找到'.$val; } //非递归方式 function bin_search($arr,$val){ if(count($arr) >= 1){ $low = 0; $high = count($arr); $time = 0; while($low <= $high){ $time++; $mid = intval(($low + $high)/2); if($val == $arr[$mid]){ return '索引:'.$mid.'<br>值为:'.$arr[$mid].'<br>查找次数:'.$time; }elseif($val > $arr[$mid]){ $low = $mid + 1; }else{ $high = $mid - 1; } } } return '未找到'.$val; } $arr = array(1,3,5,7,7,9,25,68,98,145,673,8542); echo bin_recur_search($arr, 673); echo bin_search($arr, 673); ?>
執行結果:
值为:673 查找次数:4 索引:10 值为:673 查找次数:4
相關推薦:
#javascript折半查找詳解_javascript技巧
javascript 折半查找字元在陣列中的位置(有序列表)_javascript技巧
以上是PHP如何實作折半查找演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!