Pencarian pada Array Tim PHKI Modul Dasar Pemrograman Fakultas Ilmu Komputer UDINUS Semarang
Latar Belakang • Merupakan proses yang penting karena sering dilakukan terhadap sekumpulan data yang disimpan dalam array • Ada beberapa variasi pencarian – Metoda mana yang dipakai menentukan kecepatan pencarian – Metoda yang paling sering digunakan adalah sequential search/ pencarian berurutan.
Sequential Search • Merupakan metode pencarian yang paling banyak digunakan. • Pencarian dilakukan dari elemen awal array, terurut hingga elemen akhir array. • Algoritma sequential search dapat bervariasi, yang bergantung dapat pada data. Berikut akan dibahas beberapa algoritma sequential search, seperti: – Pencarian pada data yang random atau acak – Pencarian pada data yang urut – Pencarian dengan sentinel
Permasalahan 1
(Pada Array dengan data acak/random) • Diketahui array bertipe integer A[N], yang sudah terisi. • Tuliskanlah algoritma program dengan masukan X bernilai integer dan mencari apakah X ada dalam array A secara sekuensial (berturutan)
– Jika data ditemukan program akan menghasilkan teks “Ketemu pada index …” – Jika data tidak ditemukan maka akan ditampilkan teks “Tidak ketemu” – Pencarian segera dihentikan begitu harga pertama diketemukan
• Contoh-1: N = 10, A berisi : { 1, 3, -7, 5, -8, 12, 7 ,90, 3, 5 }, X = 5 – Pemeriksaan dilakukan terhadap {1,3, -7, 5} – Output : Ketemu pada index 3
• Contoh-2: N = 5, A berisi : { 18, 6, 90, 85, 55 }, X = 100 – Pemeriksaan dilakukan terhadap {18, 6, 90, 85, 55 } – Output : Tidak ketemu
Jawab Permasalahan 1 Dari permasalahan 1 didapatkan kesimpulan sebagai berikut: • Terdapat 2 macam output, yaitu: – Ketemu, pada index … – Tidak ketemu
• Data tidak ketemu jika telah dilakukan pemeriksaan terhadap semua elemen array dari awal sampai akhir
Algoritma untuk Permasalahan 1 (Skema Pencarian Tanpa Boolean)
KAMUS i : integer {indeks untuk pencarian} N : integer {jumlah index} A : array [0…N-1] of integer X : integer {data yang akan dicari} ALGORITMA i ← 0 N ← sizeof(A) input(X) while (i < N) and (Ai ≠ X) do i ← i + 1 { i = N or Ai = X } if (Ai = X) then Output (“Ketemu pada indeks ”, i) else { Ti ≠ X } Output (“Tidak Ketemu”)
Algoritma untuk Permasalahan 1 (Skema Pencarian Dengan Boolean)
KAMUS i : integer {indeks untuk pencarian} N : integer {jumlah index} A : array [0…N-1] of integer X : integer {data yang akan dicari} ALGORITMA i ← 0 N ← sizeof(A) Found ← false { awal pencarian, belum ketemu } input(X) while (i ≤ N) and (not Found) do if (Ti = X) then Found ← true else i ← i + 1 { i > N or Found } if (Found) then Output (“Ketemu pada indeks ”, i) else Output (“Tidak Ketemu”)
Diskusikan • Buatlah algoritma untuk permasalahan 1 dengan menggunakan perulangan transversal dan kondisi, dimana menggunakan kata kunci break
Permasalahan 2
(Pada Array dengan data terurut)
• Diketahui sebuah array bertipe integer A[N], dengan isi yang terurut membesar • Tuliskanlah algoritma untuk mencari X bernilai integer, apakah harga X ada dalam A secara sekuensial mulai dari elemen pertama
– Jika data ditemukan program akan menghasilkan teks “Ketemu pada index …” – Jika tidak data tidak ditemukan maka akan ditampilkan teks “Tidak ketemu” – Pencarian segera dihentikan begitu harga pertama diketemukan
• Dengan memanfaatkan keterurutan, kondisi berhenti bisa lebih efisien (dimana x lebih besar dari nilai index maka data tidak ketemu)
Permasalahan 2 lanjutan (Pada Array dengan data terurut)
• Contoh 1: – N = 8, A berisi : { 10, 30, 50, 70, 120, 190, 311, 500}, X = 70 – Pemeriksaan dilakukan terhadap {10,30,50,70} – Output : Ketemu pada index 3
• Contoh 2: – N = 6, A berisi : { 18, 35, 55, 101, 123, 456}, X = 100 – Pemeriksaan dilakukan terhadap {18, 35, 55, 101} – Output : Tidak ketemu
Algoritma untuk Permasalahan 2 KAMUS i : integer {indeks untuk pencarian} N : integer {jumlah index} A : array [0…N-1] of integer X : integer {data yang akan dicari} ALGORITMA i ← 0 N ← sizeof(A) input(X) while (i < N) and (Ai < X) i ← i + 1 { i = N or Ti >= X } if (Ti = X ) then Output (“Ketemu pada indeks ”, i) else { Ti ≠ X Ti > X } Output (“Tidak ketemu”)
Permasalahan 3
(Pencarian berurutan dengan SENTINEL)
• Teknik ini menggunakan elemen fiktif yang diletakan pada elemen terakhir array, yang disebut SENTINEL. – Harga elemen fiktif = elemen yang dicari – Pencarian pasti ketemu maka harus dicek lagi posisi ketemu, apakah diakhir atau tidak
• Penempatan sentinel disesuaikan dengan arah pencarian(depan ke belakang atau blakang ke depan) • Teknik sentinel sangat efisien, terutama jika pencarian dilakukan sebelum penyisipan sebuah elemen yang belum terdapat di dalam array
Permasalahan 3 lanjut
(Pencarian berurutan dengan SENTINEL)
• Contoh 1: N = 7, A berisi : { 2, 4, 5, 8, 95, 30, 5}, X = 5 – A dijadikan { 2, 4, 5, 8, 95, 30, 5, 5} – Pemeriksaan dilakukan terhadap {2,4,5} – Output : Ketemu pada index 2
• Contoh 2: N = 4, A berisi : { 11, 3, 5, 8}, X = 100 – A dijadikan { 11, 3, 5, 8, 100} – Pemeriksaan dilakukan terhadap {11,3,5,8,100} – Output : Tidak ketemu
Algoritma untuk Permasalahan 3 KAMUS i : integer {indeks untuk pencarian} N : integer {jumlah index} A : array [0…N-1] of integer X : integer {data yang akan dicari} ALGORITMA i ← 0 N ← sizeof(A) input(X) TN+1 ← X {pasang sentinel } while (Ti ≠ X)do i ← i + 1 {Ti = X; harus diperiksa apakah ketemunya di sentinel } if (i< N+1) then Output (“Ketemu pada indeks ”, i) else { i = N+1 } Output (“Tidak ketemu”)
Tugas Buatlah algoritma untuk pencarian pada data seperti berikut: 1. N = 7, A berisi : { 2, 4, 5, 8, 5, 30, 5}, X = 5 2. N = 8, A berisi : { 2, 4, 5, 5, 9, 10, 15}, X = 5 Output dari data tersebut adalah: Jika ketemu: tampilkan teks “Ketemu”, tampilkan jumlah ketemu dan indeksnya Jika tidak ketemu: tampilkan teks tidak ketemu Catatan: Untuk masing-masing nomor pilihlah algoritma pencarian berurutan pada array dengan data acak, berurutan atau dengan sentinel, berikan alasan!
Referensi • Inggriani Liem, IF-ITB, Diktat Pemrograman Prosedural (2007)
THANKS
