close

Algorithm ya Utafutaji wa Binary (Binary Search) katika PHP: Maelezo, Hatua na Mfano

Algorithm ya Utafutaji wa Nambari ni njia bora ya kupata thamani maalum katika safu iliyopangwa. Mbinu hii inagawanya safu katika sehemu ndogo na kuendelea kulinganisha thamani katika nafasi ya kati ya masafa ya utafutaji na thamani lengwa. Ikiwa maadili yanalingana, thamani inayotakiwa inapatikana; vinginevyo, algorithm inaendelea kupunguza safu ya utafutaji na kurudia mchakato hadi thamani inapatikana au hakuna vipengele zaidi vinavyoachwa kuchunguza.

Hatua:

  1. Anzisha safu ya utafutaji: Anza kwa kuchagua masafa ya utafutaji kutoka nafasi ya kwanza left  hadi nafasi ya mwisho right  ya safu.
  2. Tafuta sehemu ya kati: Kokotoa sehemu ya kati kwa kuweka wastani wa left nafasi na za kulia; hii ndio sehemu ya kati ya safu ya utafutaji.
  3. Linganisha thamani: Linganisha thamani katika sehemu ya kati na thamani inayolengwa.
  4. Shikilia matokeo ya ulinganisho: Ikiwa thamani iliyo katika sehemu ya kati inalingana na thamani inayolengwa, rudisha nafasi hii. Ikiwa thamani iliyo katikati ni chini ya thamani inayolengwa, sasisha nafasi ya kushoto iwe katikati + 1 ili kutafuta nusu ya kulia. Ikiwa thamani katika sehemu ya kati ni kubwa kuliko thamani inayolengwa, sasisha nafasi ya kulia hadi katikati- 1 ili kutafuta nusu ya kushoto.
  5. Rudia: Rudia hatua ya 2 hadi 4 hadi thamani ipatikane au hakuna vipengele zaidi vya kuangalia left > right.

Faida na hasara

Manufaa:

  • Utendaji bora: Utata wa saa wa algoriti ni O(logi n), na kuifanya kuwa na ufanisi mkubwa katika kushughulikia hifadhidata kubwa.
  • Inafaa kwa seti kubwa za data: Utafutaji wa Nambari unafaa katika kupunguza idadi ya vipengee vya kuchunguza kwa haraka kwa hifadhidata kubwa.

Hasara:

  • Inatumika tu kwa safu zilizopangwa: Algorithm inafanya kazi tu kwenye safu zilizopangwa.
  • Idadi ya hatua zinazoweza kubadilika: Idadi ya hatua zinazohitajika kupata thamani inategemea nafasi yake katika safu, na inaweza kuchukua hatua nyingi kwa maadili karibu na ncha.

Mfano: Utafutaji wa Binary kwa kupata thamani 12 katika safu iliyopangwa katika 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.";  
}

Ufafanuzi wa Mfano

  1. Tunaanza na safu ya utafutaji ya awali kutoka nafasi ya kwanza left = 0 hadi nafasi ya mwisho right = 6  ya safu.
  2. Tunahesabu hatua ya kati(katikati) kwa wastani wa nafasi za kushoto na za kulia; mid = 3. Thamani ya katikati ni 12.
  3. Tunalinganisha thamani katika mid(12) na thamani inayolengwa(12) na kupata inayolingana, kwa hivyo tunarudisha nafasi ya 3.
  4. Algorithm inaisha, na tunatoa matokeo "Thamani ya 12 iliyopatikana katika nafasi ya 3."