Rumah >pembangunan bahagian belakang >C++ >Bagaimana untuk menggunakan algoritma carian binari dalam C++

Bagaimana untuk menggunakan algoritma carian binari dalam C++

WBOY
WBOYasal
2023-09-22 08:24:251119semak imbas

Bagaimana untuk menggunakan algoritma carian binari dalam C++

Cara menggunakan algoritma carian binari dalam C++

Algoritma carian binari (Binary Search) ialah algoritma carian cekap yang menggunakan The ordered set data dibahagikan kepada dua bahagian, dan setiap kali carian dilakukan di tengah set data Dengan membandingkan nilai di kedudukan tengah dengan nilai sasaran, julat carian terus disempitkan sehingga nilai sasaran ditemui atau nilai sasaran. nilai sasaran ditentukan untuk tidak wujud . Berikut akan memperkenalkan cara menggunakan algoritma carian binari dalam C++ dan memberikan contoh kod tertentu.

  1. Tentukan skop carian
    Sebelum menggunakan algoritma carian binari, anda perlu terlebih dahulu memastikan set data yang akan dicari disusun mengikut urutan. Sebagai contoh, kami mempunyai tatasusunan tersusun nombor integer di mana kami ingin mencari sasaran nilai sasaran tertentu.
  2. Tentukan fungsi carian binari
    Dalam C++, kita boleh menentukan fungsi untuk melaksanakan algoritma carian binari. Parameter input fungsi ini termasuk tatasusunan yang hendak dicari, kedudukan permulaan dan penamat tatasusunan, dan sasaran nilai sasaran. Nilai pulangan fungsi ialah indeks nilai sasaran dalam tatasusunan Jika nilai sasaran tidak wujud, nilai tertentu (seperti -1) boleh dikembalikan.

Definisi fungsi khusus adalah seperti berikut:

int binarySearch(int nums[], int start, int end, int target) {
    // 定义二分搜索的起始位置和结束位置
    int left = start;
    int right = end;
    
    while (left <= right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 如果中间位置的值等于目标值,直接返回索引
        if (nums[mid] == target) {
            return mid;
        }
        
        // 如果中间位置的值大于目标值,更新结束位置
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        
        // 如果中间位置的值小于目标值,更新起始位置
        else {
            left = mid + 1;
        }
    }
    
    // 目标值不存在,返回-1
    return -1;
}
  1. Panggil fungsi carian binari
    Dengan memanggil fungsi carian binari, kami boleh mendapatkan Indeks nilai sasaran dalam tatasusunan. Sebagai contoh, kami mempunyai nombor tatasusunan tersusun dan kami ingin mencari sasaran nilai sasaran. Anda boleh menggunakan kod berikut untuk memanggil fungsi carian binari:
int nums[] = {1, 3, 5, 7, 9};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 5;
int index = binarySearch(nums, 0, n - 1, target);

if (index != -1) {
    cout << "目标值的索引为:" << index << endl;
}
else {
    cout << "目标值不存在!" << endl;
}

Dalam kod di atas, kami mula-mula mentakrifkan nombor tatasusunan tertib, dan kemudian mengira panjang n tatasusunan. Kemudian sasaran nilai sasaran ditentukan, dan fungsi carian binari binarySearch dipanggil untuk mencari indeks nilai sasaran. Akhirnya, output adalah berdasarkan hasil yang dikembalikan oleh fungsi.

Melalui langkah di atas, kita boleh menggunakan algoritma carian binari dalam C++ untuk melaksanakan operasi carian yang cekap. Dalam aplikasi sebenar, fungsi carian binari boleh dipanggil mengikut senario dan keperluan tertentu, dan pemprosesan selanjutnya boleh dilakukan berdasarkan hasil yang dikembalikan.

Ringkasan
Algoritma carian binari ialah algoritma carian yang cekap sesuai untuk pengumpulan data yang dipesan. Dalam C++, kita boleh mencari dengan mentakrifkan fungsi carian binari dan menghantar tatasusunan untuk dicari, kedudukan permulaan, kedudukan akhir dan nilai sasaran. Dengan mengemas kini julat carian secara berterusan, indeks nilai sasaran akhirnya boleh ditemui. Kami berharap pengenalan dan contoh kod artikel ini dapat membantu pembaca lebih memahami dan menggunakan algoritma carian binari.

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

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn