Algoritma Binary Search

Binary search (pencarian biner) adalah algoritma pencarian yang efisien untuk menemukan posisi elemen tertentu dalam array (atau daftar) yang sudah diurutkan. Algoritma ini bekerja dengan membagi dua daftar secara terus-menerus hingga menemukan elemen yang dicari atau memastikan bahwa elemen tersebut tidak ada.

Algoritma Binary Search:

• Tentukan nilai tengah dari daftar.
• Bandingkan nilai tengah dengan nilai yang dicari:
• Jika data yang dicari sama, berarti ketemu.
• Jika data yang dicari lebih kecil, cari di separuh kiri.
• Jika data yang dicari lebih besar, cari di separuh kanan.
• Ulangi langkah-langkah tersebut pada bagian yang tersisa sampai ketemu atau daftar habis.

Catatan: Sebelum menggunakan algoritma binary search, perhatikan aturan pengurutan data, apakah data tersebut diurutkan secara ascending (kecil ke besar) atau descending (besar ke kecil).

Contoh Soal: Diberikan sekumpulan data yang sudah diurutkan.

• data = [3, 6, 9, 12, 15, 18, 21, 24]

Cari posisi angka 15 menggunakan Binary Search.

Tabel Penyelesaian (Ilustrasi lihat gambar 1):

Langkah	low	high	mid	data[mid]	Dibandingkan dengan 15	Keputusan
1	0	7	3	12	12 < 15	Geser ke kanan (low = 4)
2	4	7	5	18	18 > 15	Geser ke kiri (high = 4)
3	4	4	4	15	15 = 15	Ditemukan di indeks 4

Gambar 1 Ilustrasi Penyelesaian Soal Menggunakan Binary Search

Keterangan:

• low = Indeks terendah.
• high = Indeks tertinggi.
• mid = Indeks tengah, namun jika jumlah data tidak ganjil (tapi genap), maka indeks tengahnya bisa mengambil indeks tengah yang condong ke ruas kiri, ataupun juga yang condong ke ruas kanan sesuai ketentuan yang disepakati saja.
• data[mid] = Adalah data yang berada di bawah indeks mid.

Kesimpulan

• Angka 15 ditemukan di indeks 4.
• Jumlah langkah lebih sedikit dibandingkan pencarian linear biasa.

Catatan Penting

• Binary search hanya bisa digunakan pada array yang sudah terurut.
• Tidak cocok untuk array yang belum diurutkan.

Location: Kota Semarang, Jawa Tengah, Indonesia

Berbagi :