Page 154 - MODUL ALGORTIMA DAN PEMROGRAMAN

ditempatkan pada posisi terakhir dalam array, dimana elemen fiktif tersebut nilainya sama
dengan nilai elemen yang dicari.

Pada dasarnya algoritma pencarian ini sama dengan sequential search biasa yaitu mencari

elemen dengan mengeceknya satu persatu mulai dari elemen pertama hingga terakhir.
Perbedaannya yaitu terdapat penambahan elemen sentinel pada array, elemen ini dijadikan

acuan atau batas dari pencarian.
Berikut konsep sequential search search:

• Nilai yang dicari ditambahkan ke array pada indeks terakhir sebagai elemen Sentinel.

• Membandingkan setiap elemen pada array satu per satu secara berurut.
• Proses pencarian dimulai dari indeks pertama hingga indeks elemen Sentinel.

• Apabila nilai yang dicari ditemukan sebelum indeks elemen sentinel, maka nilai tersebut

ADA dan berhasil ditemukan.
• Namun apabila nilai ditemukan pada indeks elemen sentinel terdapat 2 kemungkinan.

Pertama nilai yang ditemukan adalah elemen sentinel (fiktif hanya tambahan) atau
singkatnya nilai tidak ditemukan. Kedua yaitu elemen yang dicari memang benar berada

pada indeks terakhir.

C. Binary Search

Binary search (dichotomic search) adalah metode pencarian suatu data atau elemen di

dalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search

hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu (menaik atau
menurun). Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah

yang sama atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian
dibandingkan dengan data terakhir pada bagian utama. Dalam hal ini, ada tiga kemungkinan

yang terjadi:

1. Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika
kondisi ini terpenuhi, data yang dicari berarti ditemukan.

2. Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik.
Pada keadaan ini, pencarian diteruskan pada bagian pertama.

3. Data yang dicari bernilai lebih dari elemen terakhir pada bagian pertama dalam larik. Pada
keadaan ini, pencarian diteruskan pada bagian kedua.

Agar lebih jelas, perhatikan gambar berikut.

131