Algoritma Pencarian Biner (Binary Search) di C++- Penjelasan, Contoh, dan Kode

Algoritme pencarian biner adalah cara yang lebih efisien untuk mencari elemen tertentu dalam daftar yang diurutkan. Tidak seperti pencarian linier, yang memeriksa elemen secara berurutan, pencarian biner membagi daftar menjadi dua bagian dan membandingkan elemen target dengan elemen tengah. Proses ini diulangi hingga elemen target ditemukan atau rentang pencarian menjadi kosong.

Bagaimana itu bekerja

1. Mulailah dengan seluruh daftar yang diurutkan.
2. Temukan elemen tengah dari rentang pencarian saat ini.
3. Bandingkan elemen tengah dengan nilai target.
4. Jika elemen tengah sama dengan nilai target, pencarian berhasil.
5. Jika elemen tengah lebih besar dari target, cari di paruh kiri rentang.
6. Jika elemen tengah lebih kecil dari target, cari di paruh kanan rentang.
7. Ulangi langkah 2-6 hingga elemen target ditemukan atau rentang pencarian menjadi kosong.

Contoh

Mari pertimbangkan daftar bilangan bulat yang diurutkan dan ingin mencari angka 34 menggunakan pencarian biner.

Daftar Terurut: {12, 23, 34, 45, 56, 67, 89, 90}

1. Mulailah dengan seluruh daftar.
2. Elemen tengah: 56(posisi 4). Bandingkan dengan 34.
3. 56 lebih besar dari 34. Cari di separuh kiri.
4. Elemen tengah baru: 23(posisi 1). Bandingkan dengan 34.
5. 23 lebih kecil dari 34. Cari di bagian kanan.
6. Elemen tengah baru: 45(posisi 3). Bandingkan dengan 34.
7. 45 lebih besar dari 34. Cari di separuh kiri.
8. Elemen tengah baru: 34(posisi 2). Target ditemukan.

Contoh Kode di 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 digunakan untuk menemukan angka 34 dalam daftar bilangan bulat yang diurutkan. Hasilnya adalah posisi 34 dalam daftar(posisi mulai dari 0) atau -1 jika angka tidak ditemukan.