Algoritma Carian Binari (Binary Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma carian binari ialah cara yang lebih cekap untuk mencari elemen tertentu dalam senarai disusun. Tidak seperti carian linear, yang menyemak elemen secara berurutan, carian binari membahagikan senarai kepada separuh dan membandingkan elemen sasaran dengan elemen tengah. Proses ini diulang sehingga elemen sasaran ditemui atau julat carian menjadi kosong.

Bagaimana ia berfungsi

1. Mulakan dengan keseluruhan senarai yang diisih.
2. Cari elemen tengah julat carian semasa.
3. Bandingkan elemen tengah dengan nilai sasaran.
4. Jika elemen tengah sama dengan nilai sasaran, carian berjaya.
5. Jika elemen tengah lebih besar daripada sasaran, cari di separuh kiri julat.
6. Jika elemen tengah lebih kecil daripada sasaran, cari di separuh kanan julat.
7. Ulangi langkah 2-6 sehingga elemen sasaran ditemui atau julat carian menjadi kosong.

Contoh

Mari kita pertimbangkan senarai integer yang diisih dan ingin mencari nombor 34 menggunakan carian binari.

Senarai Isih: {12, 23, 34, 45, 56, 67, 89, 90}

1. Mulakan dengan keseluruhan senarai.
2. Elemen tengah: 56(kedudukan 4). Bandingkan dengan 34.
3. 56 lebih besar daripada 34. Cari di separuh kiri.
4. Elemen tengah baharu: 23(kedudukan 1). Bandingkan dengan 34.
5. 23 adalah lebih kecil daripada 34. Cari di separuh kanan.
6. Elemen tengah baharu: 45(kedudukan 3). Bandingkan dengan 34.
7. 45 lebih besar daripada 34. Cari di separuh kiri.
8. Elemen tengah baharu: 34(kedudukan 2). Sasaran ditemui.

Contoh Kod dalam C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

Dalam contoh yang diberikan, binarySearch fungsi ini digunakan untuk mencari nombor 34 dalam senarai integer yang diisih. Hasilnya ialah kedudukan 34 dalam senarai(kedudukan bermula dari 0) atau -1 jika nombor itu tidak dijumpai.