Struktur Data dan Algoritma LanjutOleh : Shiyami M, S.Kom.

JURUSAN MANAJEMEN INFORMATIKA POLITEKNIK POS INDONESIA BANDUNG 2011

BAB I ALGORITMA PENCARIAN (SEARCHING)

1.1 Deskripsi Umum Proses Pencarian adalah menemukan nilai / data tertentu dalam sekumpulan data yang bertipe sama. Pada Bab ini akan dibahas algoritma pencarian yang paling sederhana yaitu : pencarian beruntun (Sequential Search) dan pencarian bagidua (binary search). 1.1.1 Algoritma Pencarian Beruntun (Sequential Search) Algoritma pencarian beruntun adalah proses membandingkan setiap elemen array satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan, atau seluruh elemen sudah diperiksa. Contoh : Diberikan sebuah larik L dibawah ini dengan n = 5 elemen 27 1 13 2 30 3 11 4 25 5

Misal nilai yang akan dicari adalah x = 11 Maka elemen yang dibandingkan secara berturut-turut adalah : 27, 13, 30, 11 (ditemukan) Indeks larik yang dikembalikan : idx = 4 Misal nilai yang akan dicari adalah x = 12 Maka elemen yang dibandingkan secara berturut-turut adalah : 27, 13, 30, 11, 25 (tidak ditemukan) Indeks larik yang dikembalikan : idx = -1 Terdapat 2 versi algoritma pencarian beruntun sbb : a. Versi 1 pembandingan elemen sebagai kondisi pengulangan ALGORITMA SequentialSearchV1 {Mencari keberadaan nilai x di dalam Array L[1..N]} DEKLARASI Const Nmaks = 100 {Jumlah maksimal elemen larik} L : array[1..Nmaks] of integer K : integer {pencatat indeks larik} X : integer {elemen larik yang dicari} N : integer {ukuran larik} DESKRIPSI Read (n) {banyaknya data yg akan dimasukkan kedalam larik} Read (L[K]) {memasukan elemen larik} Read (X) {data yang akan dicari} 2

K 1 while (K X) maka dapat disimpulkan bahwa (x) tidak terdapat dalam larik . bila (L[K] < X) maka proses pengulangan akan terus dilakukan hingga (L[K] = X). proses penyimpulan oencarian dilakukan di luar pengulangan dengan pernyataan (if L[K] X then ) 1.1.3 Algoritma Pencarian Bagi dua (Binary Search) Terdapat algoritma pencarian pada data terurut yang paling efisien, yaitu algoritma pencarian bagidua atau pencarian biner (binary search). Algoritma ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Metode pencarian biner ini bekerja dengan cara sebagai berikut : a. Menentukan terlebih dahulu elemen tengah larik. Elemen tengah adalah elemen dengan indeks k = (I + j) div 2, elemen tengah ini akan membentuk larik menjadi 2 bagian yaitu bagian kiri dan bagian kanan. b. Memeriksa apakah elemen tengah larik telah sama dengan data yang dicari (x) bila sama maka pencarian selesai, bila tidak sama maka pencarian data akan dilakukan pada elemen larik bagian kanan atau bagian kiri. Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut : Dimisalkan kita memiliki larik L terurut dengan 6 buah elemen yang sudah terurut menurun seperti di bawah ini : 23 i=1 18 2 14 3 10 4 7 5 3 6=j

Inisialisasi i disana adalah sebagai inisialisasi untuk indeks elemen pertama dan j adalah sebagai inisialisasi untuk indeks elemen terakhir, kedua inisialisasi ini nantinya akan berfungsi sebagai pembagi data menjadi dua bagian.

6

(i) Misalkan elemen yang dicari adalah X = 14 Langkah 1 : I = 1 dan j = 6 Indeks elemen tengah k = (I + j) div 2 = 3 (elemen yang diarsir)

23 i=1

18 2

14 3

10 4

7 5

3 6=j

Langkah 2 : Membandingkan elemen tengah L[K] dengan nilai elemen yang dicari (x) L[3] = 14 ? ya! (x ditemukan pencarian selesai) (ii) Misalkan elemen yang dicari adalah X = 10 Langkah 1 : I = 1 dan j = 6 Indeks elemen tengah k = (I + j) div 2 = 3 (elemen yang diarsir) 23 i=1 18 2 14 3 10 4 7 5 3 6=j

Langkah 2 : Membandingkan elemen tengah L[K] dengan nilai elemen yang dicari (x) L[3] = 10 ? tidak! pencarian berlanjut dengan menentukan apakah akan dilakukan pencarian di bagian kiri atau kanan larik dengan pemeriksaan membandingkan elemen tengah L[k] apakah lebih besar ( > ) dari nilai elemen yang dicari (x) L[3] > 10? Ya! Maka pencarian dilakukan di bagian kanan dengan i = k + 1 = 4 dan j = 6 (tetap) 10 i=4 7 5 3 6=j

Langkah 3 : I = 4 dan j = 6 Indeks elemen tengah k = (I + j) div 2 = 5 (elemen yang diarsir) 10 i=4 7 5 3 6=j

Langkah 4 : Membandingkan elemen tengah L[K] dengan nilai elemen yang dicari (x) L[5] = 10 ? tidak! 7

pencarian berlanjut dengan menentukan apakah akan dilakukan pencarian di bagian kiri atau kanan larik dengan pemeriksaan membandingkan elemen tengah L[k] apakah lebih besar ( > ) dari nilai elemen yang dicari (x) L[5] > 10 ? tidak! Lakukan pencarian pada larik bagian kiri dengan I = 4 (tetap) dan j = k 1 = 4 10 4 Langkah 5 : I = 4 dan j = 4 Indeks elemen tengah k = (I + j) div 2 = 4 (elemen yang diarsir) 10 4 Langkah 6 : Membandingkan elemen tengah L[K] dengan nilai elemen yang dicari (x) L[4] = 10 ? ya! (x ditemukan pencarian selesai) ALGORITMA BinarySearch {Mencari keberadaan nilai x di dalam Array L[1..N]} DEKLARASI Const Nmaks = 100 {Jumlah maksimal elemen larik} L : array[1..Nmaks] of integer K : integer {pencatat indeks larik} X : integer {elemen larik yang dicari} N : integer {ukuran larik} Idx : integer {indeks larik} Found : boolean I,j : integer DESKRIPSI Read (n) {banyaknya data yg akan dimasukkan kedalam larik} Read (L[K]) {memasukan elemen larik} Read (X) {data yang akan dicari} i1 jn while (i X) then {inilah ciri dari pencarian bagidua terurut menurun} i K+1 else j K-1 endwhile 8

if found then idx k write (X, ditemukan pada index ke :' , idx ) else write (X, 'ga ketemu nih') endif Bagaimana dengan pencarian bagidua terurut menaik ?

Algoritma pencarian bagidua terurut menaik ALGORITMA BinarySearchV2 {Mencari keberadaan nilai x di dalam Array L[1..N]} DEKLARASI Const Nmaks = 100 {Jumlah maksimal elemen larik} L : array[1..Nmaks] of integer K : integer {pencatat indeks larik} X : integer {elemen larik yang dicari} n : integer {ukuran larik} Idx : integer {indeks larik} Found : boolean DESKRIPSI Read (n) {banyaknya data yg akan dimasukkan kedalam larik} Read (L[K]) {memasukan elemen larik} Read (X) {data yang akan dicari} i1 jn while (i