Bagaimana untuk melaksanakan algoritma carian binari menggunakan PHP

Cara menggunakan PHP untuk melaksanakan algoritma carian binari

Algoritma carian binari ialah algoritma carian yang cekap, sesuai untuk mencari elemen tertentu dalam tatasusunan tertib. Artikel ini akan memperkenalkan cara menggunakan bahasa PHP untuk melaksanakan algoritma carian binari, dan melampirkan contoh kod.

Idea algoritma carian binari adalah untuk membahagikan tatasusunan kepada dua bahagian, dan kemudian menentukan bahagian mana nilai sasaran berada dengan membandingkan hubungan saiz antara nilai sasaran dan elemen tengah. Jika elemen tengah sama dengan nilai sasaran, carian berjaya jika tidak, berdasarkan perhubungan saiz antara elemen tengah dan nilai sasaran, teruskan mencari di bahagian yang sepadan sehingga nilai sasaran ditemui atau ditentukan bahawa nilai sasaran tidak wujud.

Berikut ialah contoh kod PHP yang melaksanakan algoritma carian binari:

function binary_search($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    // 目标值不存在
    return -1;
}

$arr = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 7;
$result = binary_search($arr, $target);

if ($result == -1) {
    echo "目标值不存在";
} else {
    echo "目标值在数组中的位置是：" . $result;
}

Jalankan kod di atas, output akan menjadi "Kedudukan nilai sasaran dalam tatasusunan ialah: 3", menunjukkan bahawa kedudukan indeks bagi nilai sasaran 7 dalam tatasusunan ialah 3.

Fungsi binary_search dalam kod di atas menerima dua parameter: tatasusunan tertib untuk dicari dan nilai sasaran. Fungsi ini menggunakan dua penunjuk kiri dan kanan untuk mewakili julat carian tatasusunan. Sempitkan julat carian secara berterusan melalui gelung while sehingga nilai sasaran ditemui atau ditentukan bahawa nilai sasaran tidak wujud. binary_search函数接收两个参数：待查找的有序数组和目标值。函数使用两个指针left和right来表示数组的查找范围。通过while循环不断缩小查找范围，直到找到目标值或者确定目标值不存在。

代码中的关键是通过$mid

Kunci dalam kod adalah untuk mengira kedudukan indeks elemen tengah melalui pembolehubah $mid, dan kemudian membandingkannya dengan nilai sasaran. Jika ia adalah sama, kedudukan indeks dikembalikan, jika tidak julat carian diselaraskan mengikut perhubungan saiz dan pusingan seterusnya carian binari diteruskan.

Perlu diingatkan bahawa algoritma carian binari memerlukan tatasusunan tersusun sebagai input, jika tidak, ia tidak boleh dicari dengan betul. Oleh itu, sebelum menggunakan algoritma carian binari, anda mesti memastikan tatasusunan yang hendak dicari telah disusun mengikut susunan menaik (atau menurun).

Kerumitan masa algoritma carian binari ialah O(logn), yang lebih cekap daripada O(n) algoritma carian linear. Apabila memproses data berskala besar, menggunakan algoritma carian binari boleh meningkatkan kecekapan carian dengan ketara.

Saya harap artikel ini dapat membantu pembaca memahami dan menguasai kaedah penggunaan bahasa PHP untuk melaksanakan algoritma carian binari. Dengan menggunakan algoritma carian binari secara rasional, kami boleh melakukan operasi carian dalam tatasusunan tertib dengan lebih cekap. 🎜

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma carian binari menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!