Pencarian Biner dalam C++
Pencarian biner adalah algoritma pencarian yang efisien untuk menemukan elemen tertentu dalam array yang terurut. Algoritma ini bekerja dengan membagi array secara berulang menjadi dua bagian dan membandingkan elemen tengah dengan elemen yang dicari. Jika elemen yang dicari lebih kecil dari elemen tengah, maka pencarian dilanjutkan pada bagian kiri array. Jika elemen yang dicari lebih besar dari elemen tengah, maka pencarian dilanjutkan pada bagian kanan array. Proses ini berulang sampai elemen yang dicari ditemukan atau array habis dibagi.
Keuntungan Pencarian Biner
- Efisien: Pencarian biner memiliki kompleksitas waktu logaritmik (O(log n)), yang membuatnya sangat efisien untuk array besar.
- Sederhana: Algoritma ini mudah dipahami dan diimplementasikan.
Cara Kerja Pencarian Biner
- Inisialisasi: Tentukan indeks awal (left) dan indeks akhir (right) dari array.
- Perulangan: Selama left <= right, lakukan langkah-langkah berikut:
- Hitung indeks tengah (mid) sebagai (left + right) / 2.
- Bandingkan elemen pada indeks tengah dengan elemen yang dicari.
- Jika elemen yang dicari ditemukan, kembalikan indeks tengah.
- Jika elemen yang dicari lebih kecil dari elemen tengah, set right = mid - 1.
- Jika elemen yang dicari lebih besar dari elemen tengah, set left = mid + 1.
- Kembalikan hasil: Jika perulangan selesai tanpa menemukan elemen yang dicari, kembalikan -1.
Implementasi Pencarian Biner dalam C++
Berikut adalah contoh implementasi pencarian biner dalam C++:
#include
using namespace std;
int binarySearch(int arr[], int left, int right, int target) {
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() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10;
int result = binarySearch(arr, 0, n - 1, target);
if (result == -1) {
cout << "Elemen tidak ditemukan" << endl;
} else {
cout << "Elemen ditemukan pada indeks: " << result << endl;
}
return 0;
}
Kesimpulan
Pencarian biner adalah algoritma pencarian yang sangat efisien untuk array yang terurut. Algoritma ini mudah dipahami dan diimplementasikan. Pencarian biner banyak digunakan dalam berbagai aplikasi, seperti pencarian data dalam database, sorting, dan pencarian teks.