您好,登錄后才能下訂單哦!
怎么在PHP中實(shí)現(xiàn)一個(gè)二分查找算法?很多新手對(duì)此不是很清楚,為了幫助大家解決這個(gè)難題,下面小編將為大家詳細(xì)講解,有這方面需求的人可以來學(xué)習(xí)下,希望你能有所收獲。
二分查找技術(shù),又稱為折半查找。它的前提是線性表中的記錄必須是關(guān)鍵碼有序(通常從小到達(dá)有序),線性表必須采用順序存儲(chǔ)。
基本思想:
在有序表中,取中間記錄作為比較對(duì)象,若給定值與中間記錄的關(guān)鍵字相等,則查找成功;若給定值小于中間記錄的關(guān)鍵字,則在中間記錄的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間記錄的關(guān)鍵字,則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程,直到查找成功,或所有查找區(qū)域無記錄,查找失敗為止。
代碼:
<?php //二分搜索(折半查找)算法(前提是數(shù)組必須是有序數(shù)組) 時(shí)間復(fù)雜度是 O(logn) $i = 0; //存儲(chǔ)對(duì)比的次數(shù) //@param 待查找數(shù)組 //@param 待搜索的數(shù)字 function binsearch($arr,$num){ $count = count($arr); $lower = 0; $high = $count - 1; global $i; while($lower <= $high){ $i ++; //計(jì)數(shù)器 if($arr[$lower] == $num){ return $lower; } if($arr[$high] == $num){ return $high; } $middle = intval(($lower + $high) / 2); if($num < $arr[$middle]){ $high = $middle - 1; }else if($num > $arr[$middle]){ $lower = $middle + 1; }else{ return $middle; } } //返回-1表示查找失敗 return -1; } $arr = array(0,1,16,24,35,47,59,62,73,88,99); $pos = binsearch($arr,62); print($pos); echo "<br>"; echo $i;
運(yùn)行結(jié)果:
7 3
看完上述內(nèi)容是否對(duì)您有幫助呢?如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章,請(qǐng)關(guān)注億速云行業(yè)資訊頻道,感謝您對(duì)億速云的支持。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。