close

Algoritma Binary Search (Binary Search) di PHP: Penjelasan, Langkah dan Contoh

Algoritma Pencarian Biner adalah metode yang efisien untuk menemukan nilai tertentu dalam array yang diurutkan. Pendekatan ini membagi larik menjadi bagian yang lebih kecil dan terus membandingkan nilai di posisi tengah rentang pencarian dengan nilai target. Jika nilainya cocok, nilai yang diinginkan ditemukan; jika tidak, algoritme terus mempersempit rentang pencarian dan mengulangi proses hingga nilai ditemukan atau tidak ada lagi elemen yang tersisa untuk diperiksa.

Langkah:

  1. Menginisialisasi rentang pencarian: Mulai dengan memilih rentang pencarian dari posisi pertama left  hingga posisi terakhir right  larik.
  2. Temukan titik tengah: Hitung titik tengah dengan merata-ratakan left posisi dan kanan; ini adalah titik tengah dari rentang pencarian.
  3. Bandingkan nilai: Bandingkan nilai di titik tengah dengan nilai target.
  4. Tangani hasil perbandingan: Jika nilai di titik tengah cocok dengan nilai target, kembalikan posisi ini. Jika nilai di titik tengah kurang dari nilai target, perbarui posisi kiri ke tengah + 1 untuk mencari bagian kanan. Jika nilai di titik tengah lebih besar dari nilai target, perbarui posisi kanan ke tengah- 1 untuk mencari separuh kiri.
  5. Ulangi: Ulangi langkah 2 hingga 4 hingga nilai ditemukan atau tidak ada lagi elemen yang diperiksa left > right.

Keuntungan dan kerugian

Keuntungan:

  • Performa efisien: Kompleksitas waktu algoritme adalah O(log n), membuatnya sangat efisien untuk menangani kumpulan data besar.
  • Efektif untuk kumpulan data besar: Pencarian Biner efektif dalam mengurangi jumlah elemen untuk diperiksa dengan cepat untuk kumpulan data besar.

Kekurangan:

  • Hanya berlaku untuk larik terurut: Algoritme hanya bekerja pada larik terurut.
  • Jumlah langkah variabel: Jumlah langkah yang diperlukan untuk menemukan nilai bergantung pada posisinya dalam larik, dan ini dapat memerlukan banyak langkah untuk nilai di dekat ujungnya.

Contoh: Pencarian Biner untuk menemukan nilai 12 dalam array yang diurutkan di 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.";  
}

Penjelasan Contoh

  1. Kami mulai dengan rentang pencarian awal dari posisi pertama left = 0 hingga posisi terakhir right = 6  dari array.
  2. Kami menghitung titik tengah(mid) dengan rata-rata posisi kiri dan kanan; mid = 3. Nilai di tengah adalah 12.
  3. Kami membandingkan nilai di mid(12) dengan nilai target(12) dan menemukan kecocokan, jadi kami mengembalikan posisi 3.
  4. Algoritme berakhir, dan kami menampilkan hasil "Nilai 12 ditemukan di posisi 3".