Pencarian

Adam Mukharil Bachtiar Informatics Engineering 2011

Algoritma dan Pemrograman

Searching/Pencarian

Materi

Definisi Pencarian

Pencarian Sekuensial

Pencarian Biner

Definisi Pencarian

All About Searching

Proses yang melakukan pencarian nilai dalam

Definisi Pencarian

sekumpulan data. Proses ini akan menghasilkan status DITEMUKAN atau TIDAK DITEMUKAN.

Algoritma Pencarian

•

Pencarian Sekuensial/Pencarian Linear

(Sequential search / Linear search) •

Pencarian Biner (Binary search)


Definition and Structures of Sequential Search


• Telusuri kelompok data satu per satu.

• Awali process dari data pertama. • Jika data ditemukan maka pencarian berhenti, tetapi jika tidak, pencarian diteruskan sampai data terakhir

Metode Pencarian Sekuensial

• Tanpa boolean  Tanpa sentinel

 Menggunakan sentinel • Menggunakan boolean

Ilustrasi Pencarian Sekuensial Tanpa Sentinel

Array yang akan diproses: Data

5

1

9

4

2

[1]

[2]

[3]

[4]

[5]

Data yang dicari : 9 ii+1 • Data[1] = 9? ii+1 • Data[2] = 9? i (AKHIRI PENCARIAN) • Data[3] = 9? Hasil: 9 ditemukan di Data[3]

Pencarian sekuensial tanpa sentinel 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Procedure SeqSearchTanpaSentinel (Input nama_array:tipe_array) {I.S. : elemen array [1..maks_array] sudah terdefinisi} {F.S. : menampilkan hasil pencarian (ditemukan/tidak)} Kamus: i : integer data_cari : tipedata Algoritma: input(data_cari) i  1 while(nama_array [i] ≠ data_cari) and (i < maks_array) do i  i + 1 endwhile if (nama_array[i] = data_cari) then output(data_cari,’ ditemukan pada indeks ke-’,i) else output(data_cari,’ tidak ditemukan’) endif EndProcedure

Pencarian sekuensial dengan sentinel

•

Sentinel adalah index tambahan yang ditempatkan pada index maks array + 1. Dengan demikian, data yang dicari pasti akan ditemukan.

•

Tempatkan data yang dicari di sentinel.

•

Jika data ditemukan di sentinel berarti data tidak ditemukan, dan jika data ditemukan bukan di sentinel berarti data ditemukan.

Ilustrasi pencarian dengan sentinel Data yang dicari : 9

Data

sentinel

5

1

9

4

2

9

[1]

[2]

[3]

[4]

[5]

[6]

Hasil: Data yang dicari temukan di Data[3]

Data yang dicari : 10

Data

sentinel

5

1

9

4

2

10

[1]

[2]

[3]

[4]

[5]

[6]

Hasil: Data yang dicari temukan di indeks ke-6 (sentinel). Kesimpulannya adalah data tidak ditemukan.

Pencarian sekuensial dengan sentinel 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Procedure SeqSearchSentinel (Input nama_array:tipe_array) {I.S. : elemen array [1..maks_array] sudah terdefinisi} {F.S. : menampilkan hasil pencarian (ditemukan/tidak)} Kamus: i : integer data_cari : tipedata Algoritma: input(data_cari) i  1 nama_array(maks_array + 1)  data_cari while (nama_array [i] ≠ data_cari) do i  i + 1 endwhile if (i < maks_array+1) then output(data_cari,’ ditemukan pada indeks ke-’,i) else output(data_cari,’ tidak ditemukan’) endif EndProcedure

Pencarian sekuensial menggunakan boolean

• Proses pencariannya mirip dengan

pencarian sekuensial • Melibatkan variable boolean.

Ilustrasi pencarian sekuensial menggunakan variable boolean

Array yang akan dicek: Data

5

1

9

4

2

[1]

[2]

[3]

[4]

[5]

Data yang dicari : 9 • Data[1] = 9? • Data[2] = 9? • Data[3] = 9?

Ditemukan FALSE Ditemukan  FALSE

Ditemukan  TRUE (STOP PENCARIAN)

Hasil: 9 ditemukan di Data[3]

Pencarian sekuensial menggunakan boolean 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Procedure SeqSearchBoolean (Input nama_array:tipe_array) {I.S. : elemen array [1..maks_array] sudah terdefinisi} {F.S. : menampilkan data yg dicari ditemukan atau tidak ditemukan} Kamus: i : integer ketemu : boolean data_cari : tipedata Algoritma: input(data_cari) i  1 ketemu  false while (not ketemu) and (i ≤ maks_array) do if(nama_var_array(i) = data_cari) then ketemu  true else i  i + 1 endif endwhile if (ketemu) then output(data_cari,’ ditemukan pada indeks ke-’,i) else output(data_cari,’ tidak ditemukan’) endif EndProcedure

Pencarian Biner

•

Algoritma pencarian yang membagi data menjadi dua bagian (kiri dan kanan). Dengan syarat data telah terurut.

Pencarian Biner

•

Langkahnya : 1.

Cek data yang ada di tengah (index awal + index akhir) div 2

2.

Jika data yang di tengah merupakan data yang dicari, maka pencarian berakhir. Posisi tengah adalah posisi dari data yang dicari.

3.

Jika data yang di tengah bukan merupakan data yang dicari, maka :

•

Jika data yang di tengah lebih kecil dari yang dicari, maka index awal data adalah posisi tengah +1

•

Jika data yang di tengah lebih besar dari yang dicari, maka index akhir

data adalah posisi tengah -1 4.

Ulangi dari langkah 1 sampai 3 sampai data di tengah merupakan data yang dicari atau posisi index awal sudah lebih besar dari index akhir.

Contoh Kasus Pencarian Biner

Data yang dicari : 7

Data Hasil: ?

3

7

12

15

29

[1]

[2]

[3]

[4]

[5]

Contoh Kasus Langkah 1 : Bagi array menjadi 2 bagian. Hitung posisi tengah (k) dari array untuk memulai pencarian k = (Ia + Ib) div 2 Ia : Index atas Ib : Index bawah = (1 + 5) div 2 =3 la : index bawah (untuk index) lb : index atas (untuk index)

3

7

12

15

29

[1]

[2]

[3]

[4]

[5]

Ia

k Sisi Kiri

Ib Sisi Kanan

Contoh Kasus Pencarian Biner Langkah 2 :

• Periksa data di posisi k. Jika datanya sama dengan yang dicari, maka perulangan berhenti dan data ditemukan. • Jika data tidak ditemukan di posisi k, maka – Jika data di posisi k lebih kecil dari yang dicari, maka lanjutkan

pencarian di sebelah kanan dengan cara mengganti Ia menjadi k+1 – Jika data di posisi k lebih besar dari yang dicari, maka lanjutkan pencarian di sebelah kiri dengan cara mengganti Ib menjadi k-1

3

7

1

2

Ia

Ib

Contoh Kasus Pencarian Biner

3

7

1

2

Ia

Ib

k Sisi Kiri

Sisi Kanan

Langkah 3 : ulangi langkah 1 dan langkah 2 sampai data ditemukan atau la>lb.

Hasil : 7 ditemukan di Data[2] pada perulangan ke-3.

Binary Search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Procedure BinarySearch (Input nama_array : tipe_array) {I.S. : elemen array yang terurut secara ascending sudah terdefinisi} {F.S. : menampilkan data yg dicari ditemukan atau tidak ditemukan} Kamus: Ia, Ib, k : integer ketemu : boolean data_cari : tipedata Algoritma: input(data_cari) Ia  1 Ib  maks_array ketemu  false while (not ketemu) and (Ia ≤ Ib) do k  (Ia + Ib) div 2 if (nama_var_array[k] = data_cari) then ketemu  true else if (nama_var_array[k] < data_cari) then Ia  k + 1 else Ib  k – 1 endif endif endwhile

Binary Search

27 28 29 30 31 32 33

if (ketemu) then output(data_cari,’ ditemukan pada indeks ke-’,k) else output(data_cari,’ tidak ditemukan’) endif EndProcedure

Pencarian

Recommend Documents