您好,登錄后才能下訂單哦!
本篇文章給大家分享的是有關(guān)如何在PHP項(xiàng)目中實(shí)現(xiàn)一個(gè)二分查找算法,小編覺(jué)得挺實(shí)用的,因此分享給大家學(xué)習(xí),希望大家閱讀完這篇文章后可以有所收獲,話(huà)不多說(shuō),跟著小編一起來(lái)看看吧。
二分查找法需要數(shù)組是一個(gè)有序的數(shù)組
假設(shè)我們的數(shù)組是一個(gè)遞增的數(shù)組,首先我們需要找到數(shù)組的中間位置.
1. 要知道中間位置就需要知道起始位置和結(jié)束位置,然后取出中間位置的值來(lái)和我們的值做對(duì)比。
2. 如果中間值大于我們的給定值,說(shuō)明我們的值在中間位置之前,此時(shí)需要再次二分,因?yàn)樵谥虚g之前,所以我們需要變的值是結(jié)束位置的值,此時(shí)結(jié)束位置的值應(yīng)該是我們此時(shí)的中間位置。
3. 反之,如果中間值小于我們給定的值,那么說(shuō)明給定值在中間位置之后,此時(shí)需要再次將后一部分的值進(jìn)行二分,因?yàn)樵谥虚g值之后,所以我們需要改變的值是開(kāi)始位置的值,此時(shí)開(kāi)始位置的值應(yīng)該是我們此時(shí)的中間位置,直到我們找到指定值。
4. 或者中間值等于最初的起始位置,或結(jié)束位置(此時(shí)說(shuō)明給定值未找到),下面我們來(lái)用代碼實(shí)現(xiàn)~
//循環(huán)實(shí)現(xiàn) function getValue($num,$arr) { //查找數(shù)組的中間位置 $length=count($arr); $start=0; $end=$length; $middle=floor(($start+$end)/2); //循環(huán)判斷 while($start>$end-1) { if($arr[middle]==$num) { return middle+1; } elseif($arr[middle]<$num) { //如果當(dāng)前要查找的值比當(dāng)前數(shù)組的中間值還要打,那么意味著該值在數(shù)組的后半段 //所以起始位置變成當(dāng)前的middle的值,end位置不變。 $start=$middle; $middle=floor(($start+$end)/2); } else{ //反之 $end=$middle; $middle=floor(($start+$end)/2); } } return false; }
//遞歸實(shí)現(xiàn) /* * 從數(shù)組中獲取元素值 * @param1 int $num,要查找的目標(biāo)值 * @param2 array $arr,要查找的數(shù)組 * @param3 int $start,查找的起始位置 * @param4 int $end,查找的結(jié)束位置 * @return mixed,找到了返回位置,沒(méi)找到返回false */ function getValue4($num,$arr,$start = 0,$end = 100){ //采用二分法查找 $middle = floor(($end + $start) / 2); //判斷 if($arr[$middle] == $num){ //已經(jīng)找到了,遞歸的出口 return $middle + 1; }elseif($arr[$middle] < $num){ //要查找的元素在數(shù)組的后半段 $start = $middle + 1; //邊界值 if($start >= $end){ //沒(méi)有找到,但是已經(jīng)超出邊界值,遞歸出口 return false; } //調(diào)用自己去查找:遞歸點(diǎn) return getValue4($num,$arr,$start,$end); //getValue4($num,$arr,51,100) }else{ //要查找的元素在數(shù)組的前半段 $end = $middle - 1; //判斷邊界值 if($end < 0)return false; //調(diào)用自己:遞歸點(diǎn) return getValue4($num,$arr,$start,$end); //getValue4($num,$arr,0,49) } //都沒(méi)有找到 return false; }
以上就是如何在PHP項(xiàng)目中實(shí)現(xiàn)一個(gè)二分查找算法,小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘9ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀(guā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)容。