PHP實(shí)現(xiàn)二分查找算法的方法是什么

這篇文章主要介紹了PHP實(shí)現(xiàn)二分查找算法的方法是什么，具有一定借鑒價(jià)值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。

二分查找又稱折半查找，二分查找算法要求數(shù)據(jù)必須是有序的，以下是php實(shí)現(xiàn)二分查找算法的代碼。

一：遞歸方式

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
$low = 0;
$high = count($array)-1;
function bin_search($array, $low, $high, $target){
    if ( $low <= $high){
        var_dump($low, $high);echo "\n";
        $mid =  intval(($low+$high)/2 );
        if ($array[$mid] ==  $target){
            return true;
        }elseif ( $target < $array[$mid]){
            return  bin_search($array, $low,  $mid-1, $target);
        }else{
            return  bin_search($array, $mid+ 1, $high, $target);
        }
    }
    return false;
}
$find = bin_search($array, $low, $high, $target);
var_dump($find);

執(zhí)行結(jié)果

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

我們看到，經(jīng)過4次二分查找，查找區(qū)間不斷折半，最終找到了$target。

二：循環(huán)方式

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$mid] == $target){
                $find = true;
                break;
            } elseif ($array[$mid] < $target){
                $low = $mid+1;
            } elseif ($array[$mid] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);

執(zhí)行結(jié)果

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

我們看到，兩種方式過程和結(jié)果相同。下面我們來測試下針對關(guān)聯(lián)數(shù)組的二分查找算法：

$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];
$target = 19;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $key_map = array_keys($array);
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$key_map[$mid]] == $target){
                $find = true;
                break;
            } elseif ($array[$key_map[$mid]] < $target){
                $low = $mid+1;
            } elseif ($array[$key_map[$mid]] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);
執(zhí)行結(jié)果
int(0)
int(8)
int(5)
int(8)
bool(true)

兩次二分查找，找到了$target，針對關(guān)聯(lián)數(shù)組，我們使用了php的array_keys函數(shù)獲得這個(gè)關(guān)聯(lián)有序數(shù)組的key，通過key間接比對$target和$array的值。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享PHP實(shí)現(xiàn)二分查找算法的方法是什么內(nèi)容對大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，遇到問題就找億速云，詳細(xì)的解決方法等著你來學(xué)習(xí)!