Carian binari dalam PHP

Apakah carian binari?

Carian binari ialah algoritma carian yang digunakan untuk mencari dengan cekap kedudukan nilai sasaran dalam tatasusunan (atau senarai) yang diisih. Ia berfungsi dengan membahagikan julat carian berulang kali kepada separuh dan membandingkan elemen tengah dengan nilai sasaran.

Algoritma carian binari mengikut langkah berikut:

• Mulakan dengan keseluruhan tatasusunan yang diisih.

• Tetapkan penunjuk kiri ke elemen pertama tatasusunan dan penunjuk kanan ke elemen terakhir.

• Kira indeks tengah sebagai purata penunjuk kiri dan kanan (bahagian integer).

• Membandingkan nilai pada indeks tengah dengan nilai sasaran.

• Jika nilai perantaraan adalah sama dengan nilai sasaran, carian berjaya dan algoritma mengembalikan indeks.

• Jika nilai sasaran lebih besar daripada nilai tengah, hilangkan separuh kiri julat carian dengan mengemas kini penuding kiri ke pertengahan + 1.

• Jika nilai sasaran kurang daripada nilai tengah, hilangkan separuh kanan julat carian dengan mengemas kini penunjuk kanan ke pertengahan - 1.

• Ulang langkah 3 hingga 7 sehingga nilai sasaran ditemui atau julat carian kosong (penunjuk kiri lebih besar daripada penunjuk kanan).

• Jika julat carian kosong dan nilai sasaran tidak ditemui, algoritma membuat kesimpulan bahawa nilai sasaran tidak wujud dalam tatasusunan dan mengembalikan -1 atau petunjuk yang sesuai.

Carian binari ialah algoritma yang sangat cekap dengan kerumitan masa O(log n), dengan n ialah bilangan elemen dalam tatasusunan. Ia amat berkesan untuk tatasusunan diisih yang besar kerana ia mengecilkan julat carian dengan cepat dengan membahagikannya kepada separuh pada setiap langkah, membolehkan carian pantas walaupun dengan sejumlah besar elemen.

Program PHP carian binari

Kaedah 1 - Gunakan lelaran

Contoh

<?php
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   while ($left <= $right) {
      $mid = floor(($left + $right) / 2);
      // Check if the target value is found at the middle index
      if ($arr[$mid] === $target) {
         return $mid;
      }
      // If the target is greater, ignore the left half
      if ($arr[$mid] < $target) {
         $left = $mid + 1;
      }
      // If the target is smaller, ignore the right half
      else {
         $right = $mid - 1;
      }
   }
   // Target value not found in the array
   return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.<br>";
} else {
   echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Output

Target value found at index 9.
Target value not found in the array.

Kaedah 2 - Gunakan rekursi

Contoh

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
   if ($left > $right) {
      // Target value not found in the array
      return -1;
   }
   $mid = floor(($left + $right) / 2);
   // Check if the target value is found at the middle index
   if ($arr[$mid] === $target) {
      return $mid;
   }
   // If the target is greater, search the right half
   if ($arr[$mid] < $target) {
      return binarySearchRecursive($arr, $target, $mid + 1, $right);
   }
   // If the target is smaller, search the left half
   return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Output

Target value found at index 4.

KESIMPULAN

Ringkasnya, carian binari ialah algoritma berkuasa yang boleh mencari nilai sasaran dengan cekap dalam tatasusunan yang disusun. Ia menyediakan dua pelaksanaan biasa: berulang dan rekursif. Kaedah lelaran menggunakan gelung sementara untuk membahagi julat carian berulang kali kepada separuh sehingga nilai sasaran ditemui atau julat menjadi kosong. Ia mempunyai pelaksanaan yang mudah dan sesuai untuk kebanyakan senario. Sebaliknya, kaedah rekursif menggunakan fungsi rekursif untuk melakukan carian binari. Ia mengikut logik yang sama seperti kaedah lelaran, tetapi menggunakan panggilan fungsi dan bukannya gelung. Carian binari rekursif menyediakan pelaksanaan yang lebih bersih, tetapi mungkin mempunyai overhed yang lebih tinggi sedikit disebabkan oleh manipulasi tindanan panggilan fungsi. Secara keseluruhan, kedua-dua kaedah menyediakan cara yang cekap dan boleh dipercayai untuk melaksanakan operasi carian binari.

Atas ialah kandungan terperinci Carian binari dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!