SEARCHING 05/19/2019
SEARCHING (PENCARIAN)
Ada beberapa pencarian yang akan kita uraikan disini:
• Pencarian Beruntun (Sekuensial Search)
• Pencarian Beruntun dengan sentinel
• Pencarian Bagi dua (Binary Search)
Pencarian Beruntun (Sekuensial Search)
Konsep : membandingkan setiap setiap elemen larik satu per satu secara urut (beruntun), mulai dari
elemen pertama sampai dengan elemen yang terakhir. Ada 2 macam pencarian beruntun,yaitu pencarian
pada array yang sudah terurut, dan pencari an pada array yang belum terurut.
Contoh 1:
1
SEARCHING 05/19/2019
Contoh 2:
Pencarian Beruntun Dengan Sentinel
Algoritma ini adalah pengembangan dari algoritma pencarian beruntun. Yang dimaksud dengan sentinel
adalah elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir dari larik tersebut. Jadi jika
elemen terakhir dari larik adalah L[N], maka sentinel diletakkan pada elemen L[N+1]. Akibatnya proses
pencarian akan selalu menemukan data yang dicari, akan tetapi harus selalu diperiksa letak data yang
ditemukan, apakah:
1. Di antara elemen-elemen larik yang sesungguhnya(antara L[1] sampai dengan L[N])
2. Pada elemen fiktif [L[N+1]]
Sentinel
Misal diberikan data sebagai berikut:
5 1 9 4 2 9
1 2 3 4 5 6
Data yang dicari : 9
Data yang dicari akan ditempatkan pada sentinel (dari contoh diatas berarti data 9 akan ditempatkan pada
indeks ke-6)
Proses pencarian masih sama seperti Sekuensial Search tanpa sentinel, hanya saja data yang dicari pasti
selalu ditemukan. Untuk mengetahui data yang dicari itu ada atau tidak, di cek indeksnya, jika indeksnya
bukan berada di sentinel, maka data yang dicari ada/ditemukan, tapi berada di sentinel berarti data
yang dicari tidak ada/tidak ditemukan.
2
SEARCHING 05/19/2019
Contoh 3:
Pencarian Bagi Dua (Binary Search)
Syarat: Data harus terurut
Salah satu keuntungan data yang terurut adalah memudahkan pencarian, yang dalam hal ini adalah
pencarian bagi dua. Sebenarnya dalam kehidupan sehari-hari kita sering menerapkan algoritma ini. Untuk
mencari kata tertentu dalam kamus (misalnya kamus bahasa Inggris), kita tidak membuka kamus tersebut
dari halaman awal sampai halaman akhir satu persatu, namun kita mencarinya dengan cara membelah
atau membagi halaman-halaman buku tersebut. Begitu seterusnya sampai kita menemukan kata yang
dicari.
Prinsip Pencarian:
Kita asumsikan data sudah terurut, misalkan terurut menurun. Kita menyebut indeks terkecil sebagai
indeks ujung paling kiri, dan indeks terbesar sebagai indeks ujung paling kanan. Misalkan indeks kiri Ia dan
indeks kanan adalah Ib. Pada mulanya Ia adalah 0 dan Ib adalah N.
Langkah 1:
Bagi 2 elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k=(Ia+Ib) div 2.
(Elemen tengah, L[k], membagi larik menjadi 2 bagian L[Ia…k-1] dan bagian kanan L[k+1…Ib]).
Langkah 2:
Periksa apakah L[k]=X. Jika L[k]=X, pencarian dihentikan sebab X sudah ditemukan, tetapi jika tidak , harus
ditentukan apakah pencarian pada larik bagian kiri atau larik bagian kanan. Jika L[k] < X maka pencarian
dilakukan pada larik kiri. Sebaliknya jika L[k] >X maka pencarian dilakukan pada larik bagian kanan.
Langkah 3:
Ulangi langkah 1 sampai X atau Ia>Ib.
3
SEARCHING 05/19/2019
Keterangan : L = low; M = mid; H = high
Contoh 4: