Algoritma Binary Search (Pencarian Biner) adalah metode pencarian yang efisien untuk menemukan posisi suatu elemen dalam daftar yang sudah terurut (biasanya dalam urutan menaik atau menurun). Binary Search bekerja dengan prinsip membagi dua ruang pencarian setiap kali langkah pencarian dilakukan.

Cara Kerja Binary Search

Berikut adalah penjelasan detail cara kerja algoritma Binary Search, langkah demi langkah:

1. Persiapan

• Pastikan daftar data dalam urutan terurut (misalnya dari kecil ke besar).

• Siapkan tiga indeks:

  • low: indeks awal (biasanya 0)

  • high: indeks akhir (panjang array – 1)

  • mid: indeks tengah yang dihitung setiap langkah

2. Langkah-langkah Binary Search

Misalnya kita ingin mencari elemen x dalam array A yang sudah terurut:

Langkah 1: Hitung indeks tengah

mid = (low + high) // 2

Langkah 2: Bandingkan elemen tengah dengan target (x)

• Jika A[mid] == x: berarti elemen ditemukan, pencarian selesai.

• Jika x < A[mid]: elemen ada di sebelah kiri → ubah high = mid - 1

• Jika x > A[mid]: elemen ada di sebelah kanan → ubah low = mid + 1

Langkah 3: Ulangi

• Ulangi proses dari langkah 1 dengan batas low dan high yang baru sampai:

  • Elemen ditemukan, atau

  • low > high → elemen tidak ditemukan

Contoh Langkah Demi Langkah

Array:

A = [2, 4, 6, 8, 10, 12, 14]
x = 10

• Langkah 1:
  low = 0, high = 6
mid = (0+6)//2 = 3 → A[3] = 8
  Karena 10 > 8, pencarian pindah ke kanan → low = 4

• Langkah 2:
  low = 4, high = 6
mid = (4+6)//2 = 5 → A[5] = 12
  Karena 10 < 12, pencarian pindah ke kiri → high = 4

• Langkah 3:
  low = 4, high = 4
mid = (4+4)//2 = 4 → A[4] = 10
  Ketemu! Elemen ditemukan di indeks ke-4.

Kompleksitas Waktu

• Best case: O(1) → langsung ketemu di tengah

• Average/Worst case: O(log n) → karena tiap langkah membagi dua ruang pencarian

Berikut adalah pseudocode dan contoh implementasi Binary Search dalam Python:

function BinarySearch(A, x):
low ← 0
high ← length(A) – 1

while low ≤ high:
mid ← (low + high) // 2
if A[mid] == x:
return mid // elemen ditemukan
else if x < A[mid]:
high ← mid – 1
else:
low ← mid + 1

return -1 // elemen tidak ditemukan

Implementasi Python (Versi Iteratif)

def binary_search(arr, x):
low = 0
high = len(arr) – 1

while low <= high:
mid = (low + high) // 2

if arr[mid] == x:
return mid # posisi ditemukan
elif x < arr[mid]:
high = mid – 1
else:
low = mid + 1

return -1 # tidak ditemukan

# Contoh penggunaan
data = [2, 4, 6, 8, 10, 12, 14]
target = 10

hasil = binary_search(data, target)
if hasil != -1:
print(f”Elemen {target} ditemukan di indeks {hasil}”)
else:
print(“Elemen tidak ditemukan”)

Implementasi Python (Versi Rekursif)

def binary_search_recursive(arr, x, low, high):
if low > high:
return -1 # elemen tidak ditemukan

mid = (low + high) // 2

if arr[mid] == x:
return mid
elif x < arr[mid]:
return binary_search_recursive(arr, x, low, mid – 1)
else:
return binary_search_recursive(arr, x, mid + 1, high)

# Contoh penggunaan
data = [2, 4, 6, 8, 10, 12, 14]
target = 10

hasil = binary_search_recursive(data, target, 0, len(data) – 1)
if hasil != -1:
print(f”Elemen {target} ditemukan di indeks {hasil}”)
else:
print(“Elemen tidak ditemukan”)

Syarat Binary Search

Berikut adalah syarat-syarat Binary Search secara detail, agar algoritma ini bisa bekerja dengan benar dan efisien:

1. Data Harus Sudah Terurut

Penjelasan:

• Ini adalah syarat utama. Binary Search hanya bisa dilakukan jika data berada dalam urutan menaik (ascending) atau menurun (descending).

• Jika data tidak terurut, hasil pencarian bisa tidak valid atau salah.

Contoh:

# Bisa (urutan menaik)
[2, 4, 6, 8, 10, 12]

# Tidak bisa
[6, 2, 12, 4, 8, 10] ← ini harus diurutkan dulu

2. Akses ke Data Secara Acak (Random Access)

Penjelasan:

• Binary Search bekerja optimal jika elemen bisa diakses langsung dengan indeks, seperti pada array atau list.

• Pada struktur data seperti linked list, binary search tidak efisien, karena kita tidak bisa langsung lompat ke elemen tengah tanpa menelusuri satu per satu.

3. Tahu Posisi Awal dan Akhir (Indeks)

Penjelasan:

• Binary Search memerlukan batas low (awal) dan high (akhir) untuk menentukan ruang pencarian.

• Tanpa batas ini, algoritma tidak bisa menghitung titik tengah (mid).

4. Tidak Ada Duplikasi yang Mengganggu (Opsional)

Penjelasan:

• Binary Search tetap bisa bekerja dengan data duplikat, tapi:

  • Jika kita mencari semua posisi dari elemen yang sama (misal ada dua angka 10), maka versi dasar dari Binary Search tidak cukup.

  • Kita perlu memodifikasi algoritma untuk menemukan kemunculan pertama/terakhir elemen tersebut (disebut modified binary search).

5. Komparasi (Perbandingan) Harus Didefinisikan dengan Jelas

Penjelasan:

• Binary Search membandingkan elemen tengah dengan target.

• Artinya, tipe data harus bisa dibandingkan (pakai operator <, >, ==).

• Untuk tipe data khusus (misalnya objek), kita harus menentukan cara membandingkannya.

6. Tidak Cocok untuk Data yang Terus Berubah

Penjelasan:

• Jika data sering berubah (bertambah, dihapus, atau diacak), urutan bisa rusak.

• Setelah perubahan, kita perlu mengurutkan ulang data sebelum pakai binary search lagi.

Kesimpulan:

Syarat	Wajib?	Penjelasan Singkat
Data terurut	✔️	Harus ascending/descending
Akses acak	✔️	Array/list, bukan linked list
Indeks awal & akhir	✔️	Untuk hitung midpoint
Duplikasi tertangani	⚠️	Perlu modifikasi jika ingin semua hasil
Bisa dibandingkan	✔️	Data harus bisa dibandingkan
Data stabil (tidak berubah-ubah)	⚠️	Jika sering berubah, perlu sortir ulang

Penutup

Algoritma Binary Search adalah metode pencarian yang sangat efisien untuk menemukan elemen dalam daftar yang terurut, dengan kompleksitas waktu O(log n). Keunggulannya terletak pada kecepatan, karena ia membagi ruang pencarian menjadi dua setiap langkahnya. Namun, kelemahannya adalah data harus sudah terurut sebelumnya.

Dengan memahami konsep, cara kerja, serta implementasinya, kamu bisa menggunakan Binary Search dalam berbagai aplikasi seperti pencarian data, pemrograman kompetitif, dan algoritma berbasis pencarian lainnya.