close

Algoritma Carian Binari (Binary Search) dalam PHP: Penjelasan, Langkah dan Contoh

Algoritma Carian Binari ialah kaedah yang cekap untuk mencari nilai tertentu dalam tatasusunan yang disusun. Pendekatan ini membahagikan tatasusunan kepada bahagian yang lebih kecil dan terus membandingkan nilai pada kedudukan tengah julat carian dengan nilai sasaran. Jika nilai sepadan, nilai yang dikehendaki ditemui; jika tidak, algoritma terus mengecilkan julat carian dan mengulangi proses sehingga nilai ditemui atau tiada lagi elemen yang tinggal untuk diperiksa.

Langkah-langkah:

  1. Mulakan julat carian: Mulakan dengan memilih julat carian dari kedudukan pertama left  hingga kedudukan terakhir right  tatasusunan.
  2. Cari titik tengah: Kira titik tengah dengan purata left kedudukan dan kanan; ini ialah titik tengah julat carian.
  3. Bandingkan nilai: Bandingkan nilai di titik tengah dengan nilai sasaran.
  4. Kendalikan hasil perbandingan: Jika nilai di titik tengah sepadan dengan nilai sasaran, kembalikan kedudukan ini. Jika nilai di titik tengah kurang daripada nilai sasaran, kemas kini kedudukan kiri ke tengah + 1 untuk mencari separuh kanan. Jika nilai pada titik tengah lebih besar daripada nilai sasaran, kemas kini kedudukan kanan ke tengah- 1 untuk mencari bahagian kiri.
  5. Ulang: Ulang langkah 2 hingga 4 sehingga nilai ditemui atau tiada lagi elemen untuk diperiksa left > right.

Kelebihan dan kekurangan

Kelebihan:

  • Prestasi cekap: Kerumitan masa algoritma ialah O(log n), menjadikannya sangat cekap untuk mengendalikan set data yang besar.
  • Berkesan untuk set data yang besar: Carian Binari berkesan dalam mengurangkan bilangan elemen untuk diperiksa dengan cepat untuk set data yang besar.

Kelemahan:

  • Terpakai hanya untuk tatasusunan yang diisih: Algoritma hanya berfungsi pada tatasusunan yang diisih.
  • Bilangan langkah yang berubah-ubah: Bilangan langkah yang diperlukan untuk mencari nilai bergantung pada kedudukannya dalam tatasusunan dan ia boleh mengambil banyak langkah untuk nilai berhampiran penghujung.

Contoh: Carian Binari untuk mencari nilai 12 dalam tatasusunan yang disusun dalam 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. Kita mulakan dengan julat carian awal dari kedudukan pertama left = 0 hingga kedudukan terakhir right = 6  tatasusunan.
  2. Kami mengira titik tengah(tengah) dengan purata kedudukan kiri dan kanan; mid = 3. Nilai pada pertengahan ialah 12.
  3. Kami membandingkan nilai pada mid(12) dengan nilai sasaran(12) dan mencari padanan, jadi kami mengembalikan kedudukan 3.
  4. Algoritma tamat, dan kami mengeluarkan hasil "Nilai 12 ditemui pada kedudukan 3."