close

(Binary Search) PHP'de İkili Arama Algoritması: Açıklama, Adımlar ve Örnek

İkili Arama algoritması, sıralanmış bir dizide belirli bir değeri bulmak için etkili bir yöntemdir. Bu yaklaşım, diziyi daha küçük parçalara böler ve sürekli olarak arama aralığının orta konumundaki değeri hedef değerle karşılaştırır. Değerler eşleşirse istenilen değer bulunur; aksi takdirde, algoritma arama aralığını daraltmaya devam eder ve değer bulunana veya incelenecek başka öğe kalmayana kadar işlemi tekrarlar.

Adımlar:

  1. Arama aralığını başlat:  Dizinin ilk konumundan left  son konumuna kadar arama aralığını seçerek başlayın. right
  2. Orta noktayı bulun: ve doğru konumların ortalamasını alarak orta noktayı hesaplayın left ; bu, arama aralığının orta noktasıdır.
  3. Değerleri karşılaştırın: Orta noktadaki değeri hedef değerle karşılaştırın.
  4. Karşılaştırma sonucunu işle: Orta noktadaki değer hedef değerle eşleşiyorsa, bu konumu döndürün. Orta noktadaki değer hedef değerden küçükse, sağ yarıyı aramak için sol konumu orta + 1 olarak güncelleyin. Orta noktadaki değer hedef değerden büyükse, sol yarıyı aramak için sağ konumu orta- 1 olarak güncelleyin.
  5. Tekrarla: Değer bulunana veya kontrol edilecek başka öğe kalmayana kadar 2 ila 4 arasındaki adımları tekrarlayın left > right.

Avantajlar ve dezavantajlar

Avantajlar:

  • Verimli performans: Algoritmanın zaman karmaşıklığı O(log n), bu da onu büyük veri kümelerini işlemek için oldukça verimli kılar.
  • Büyük veri kümeleri için etkilidir: İkili Arama, büyük veri kümeleri için hızlı bir şekilde incelenecek öğelerin sayısını azaltmada etkilidir.

Dezavantajları:

  • Yalnızca sıralanmış diziler için geçerlidir: Algoritma yalnızca sıralanmış dizilerde çalışır.
  • Değişken adım sayısı: Değeri bulmak için gereken adım sayısı, dizideki konumuna bağlıdır ve uçlara yakın değerler için birçok adım atabilir.

Örnek: PHP'de sıralanmış bir dizide 12 değerini bulmak için İkili Arama 

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.";  
}

Örnek Açıklama

  1.  Dizinin ilk konumundan left = 0 son konumuna kadar ilk arama aralığıyla başlıyoruz. right = 6
  2. Sol ve sağ konumların ortalamasını alarak orta noktayı(orta) hesaplıyoruz; mid = 3. Ortadaki değer 12'dir.
  3. )' deki değeri hedef değerle(12) karşılaştırır mid(12 ve bir eşleşme buluruz, böylece 3. konumu döndürürüz.
  4. Algoritma sona erer ve "3. konumda bulunan Değer 12" sonucunu veririz.