Jelaskan konsep pencarian biner.
Pencarian biner adalah algoritma pencarian yang digunakan untuk menemukan nilai tertentu dalam daftar atau array yang diurutkan. Algoritme bekerja dengan membagi daftar menjadi dua dan kemudian memeriksa apakah nilai yang dicari lebih besar atau kurang dari elemen tengah daftar. Proses ini diulangi hingga nilai ditemukan atau tidak ada lagi elemen yang perlu diperiksa.

Keuntungan utama dari penelusuran biner adalah ia memiliki kompleksitas waktu O(log n), yang jauh lebih cepat daripada penelusuran linier yang memiliki kompleksitas waktu O(n). Hal ini membuat pencarian biner sangat berguna untuk kumpulan data besar yang mengutamakan kinerja.

Untuk menerapkan pencarian biner, daftar atau larik harus diurutkan terlebih dahulu dalam urutan menaik atau menurun. Algoritme kemudian memeriksa elemen tengah daftar dan membandingkannya dengan nilai yang dicari. Jika nilainya lebih besar dari elemen tengah, algoritme akan mengulangi pencarian di bagian kanan daftar. Jika nilainya kurang dari elemen tengah, algoritme mengulangi pencarian di bagian kiri daftar. Proses ini diulangi hingga nilai ditemukan atau tidak ada lagi elemen yang perlu diperiksa.

Pencarian biner dapat diimplementasikan secara rekursif atau iteratif. Dalam implementasi rekursif, algoritme memanggil dirinya sendiri pada sub-daftar hingga nilainya ditemukan. Dalam implementasi berulang, algoritme menggunakan perulangan untuk membagi daftar menjadi dua berulang kali hingga nilainya ditemukan.