Searching : Binary Search

Binary search (pencarian bagi dua) adalah teknik pencarian yang diterapkan hanya pada elemen array yang telah terurut (sorted).
Prinsip binary search :
1. Mula-mula ambil posisi awal = 1 dan posisi akhir = N.
    Posisi tengah = (posisi awal + posisi akhir) / 2
2. Bandingkan data yang dicari (x) dengan data tengah.
    Jika x < data tengah, proses dilakukan kembali tetapi posisi akhir = posisi tengah - 1.
    Jika x > data tengah, proses dilakukan kembali tetapi posisi awal = posisi tengah + 1.
3. Demikian seterusnya hingga :
    Data tengah = x, yang berarti data ditemukan.
    Posisi awal > Posisi akhir, yang berarti data tidak ditemukan

Data : 3   9   11   12   15   17   20   23   31   35
Misal ingin dicari data 17 :
Posisi awal = 1
Posisi akhir = 10
Posisi tengah = (posisi awal + posisi akhir) / 2 = (1 + 10) / 2 = 5
Data tengah = 15

Karena x > data tengah → 17 > 15, maka proses dilanjutkan dengan :
Posisi awal = posisi tengah + 1 = 5 + 1 = 6
Posisi akhir = 10
Posisi tengah = (6 + 10) / 2 = 8

Karena x < data tengah → 17 < 23, maka proses dilanjutkan dengan :
Posisi awal = 6
Posisi akhir = 8 - 1 = 7
Posisi tengah = (6 + 7) / 2 = 6

Karena x = data tengah → 17 = 17. Maka data ditemukan pada indeks ke-6.