close

Algartam Cuardaigh Dénártha (Binary Search) i PHP: Míniú, Céimeanna agus Sampla

Is modh éifeachtach é an t-algartam Cuardach Dénártha chun luach sonrach a aimsiú in eagar sórtáilte. Roinneann an cur chuige seo an t-eagar i gcodanna níos lú agus déanann sé comparáid leanúnach idir an luach ag suíomh lár an raon cuardaigh agus an luach sprice. Má mheaitseálann na luachanna, faightear an luach inmhianaithe; ar shlí eile, leanann an algartam ag caol síos an raon cuardaigh agus athuair an próiseas go dtí go bhfaightear an luach nó nach bhfuil níos mó eilimintí fágtha le scrúdú.

Céimeanna:

  1. Tosaigh an raon cuardaigh: Tosaigh tríd an raon cuardaigh a roghnú ón gcéad áit left  go dtí an suíomh deireanach right  den eagar.
  2. Faigh an lárphointe: Ríomh an lárphointe trí na left suíomhanna ar an meán agus ar dheis; is é seo lárphointe an raon cuardaigh.
  3. Cuir luachanna i gcomparáid: Cuir an luach ag an lárphointe i gcomparáid leis an spriocluach.
  4. Déan toradh na comparáide a láimhseáil: Má thagann an luach ag an lárphointe leis an spriocluach, cuir an suíomh seo ar ais. Má tá an luach ag an lárphointe níos lú ná an spriocluach, nuashonraigh an suíomh clé go lár + 1 chun an leath ceart a chuardach. Má tá an luach ag an lárphointe níos mó ná an spriocluach, nuashonraigh an suíomh ceart go lár- 1 chun an leath chlé a chuardach.
  5. Déan: Déan céimeanna 2 go 4 arís go dtí go bhfaighfear an luach nó nach bhfuil a thuilleadh eilimintí le seiceáil left > right.

Buntáistí agus míbhuntáistí

Buntáistí:

  • Feidhmíocht éifeachtach: Is é O(log n) castacht ama an algartam, rud a fhágann go bhfuil sé an-éifeachtach chun tacair shonraí mhóra a láimhseáil.
  • Éifeachtach do thacair shonraí mhóra: Tá Cuardach Dénártha éifeachtach chun líon na n-eilimintí a scrúdú go tapa le haghaidh tacair shonraí móra a laghdú.

Míbhuntáistí:

  • Infheidhme maidir le heagair shórtáilte amháin: Ní oibríonn an algartam ach ar eagair shórtáilte.
  • Líon athraitheach céimeanna: Braitheann líon na gcéimeanna a theastaíonn chun an luach a fháil ar a shuíomh san eagar, agus is féidir go leor céimeanna a ghlacadh le haghaidh luachanna gar do na foircinn.

Sampla: Dénártha Déan cuardach chun an luach 12 a fháil in eagar sórtáilte i PHP 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

Míniú ar an Sampla

  1. Tosaímid leis an raon cuardaigh tosaigh ón gcéad áit left = 0 go dtí an suíomh deireanach right = 6  den eagar.
  2. Ríomhaimid an lárphointe(lár) trí mheán na suíomhanna clé agus ar dheis; mid = 3. Is é 12 an luach ag lár.
  3. Déanaimid comparáid idir an luach ag mid(12) agus an luach sprice(12) agus aimsímid meaitseáil, mar sin tugaimid suíomh 3 ar ais.
  4. Críochnaíonn an algartam, agus aschuirimid an toradh "Luach 12 le fáil ag seasamh 3."