1. Tujuan
Setelah mempelajari modul ini, maka anda diharapkan mampu
1. Menjelaskan beberapa algoritma pencarian
2. Meaplikasikan algoritma dalam pemrograman
2. Teori Dasar
Pencarian dalam sebuah program akan sangat menguntungkan bagi pemrogram apabila akan
membuat sebuah program yang mengharuskan adanya pencarian data tertentu. Pencarian data
tertentu yang terkandung di dalam array merupakan hal yang banyak ditemukan dalam kasuskasus pemrograman. Metode pencarian data di dalam array dapat dibagi menjadi dua, yaitu
metode pencarian beruntun (sequential search) dan metode pencarian bagi dua/pencarian biner
(binary search). Berikut ini penjelasannya dari kedua metode tersebut.
A. Metode Pencarian Beruntun
Metode ini banyak digunakan karena efektif untuk melakukan pencarian dari
sekumpulan data, baik data sudah terurut maupun yang belum terurut atau masih acak. Bila
dibandingkan dengan yang lainnya, metode ini memiliki cara kerja yang relatif mudah untuk
dipahami. Dalam metode ini, data yang dicari akan dibandingkandengan seluruh elemen
array yang ada. Sebagai contoh, apabila kita memiliki array A yang memiliki indeks 1
sampai n dan kita akan mencari nilai x di dalam array tersebut, maka nilai x tersebut akan
dibandingkan dengan nilai A[1] sampai A[n]. Dalam metode ini juga diterapkan bahwa
apabila data ditemukan pada indeks tertentu, maka proses pencarian akan dihentikan. Hal ini
bertujuan agar proses pembandingan nilai tidak dilakukan sampai indeks terakhir karena nilai
yang dicari telah ditemukan.Agar lebih memperjelas, perhatikan gambar proses pencarian
data berikut.
Setelah mempelajari modul ini, maka anda diharapkan mampu
1. Menjelaskan beberapa algoritma pencarian
2. Meaplikasikan algoritma dalam pemrograman
2. Teori Dasar
Pencarian dalam sebuah program akan sangat menguntungkan bagi pemrogram apabila akan
membuat sebuah program yang mengharuskan adanya pencarian data tertentu. Pencarian data
tertentu yang terkandung di dalam array merupakan hal yang banyak ditemukan dalam kasuskasus pemrograman. Metode pencarian data di dalam array dapat dibagi menjadi dua, yaitu
metode pencarian beruntun (sequential search) dan metode pencarian bagi dua/pencarian biner
(binary search). Berikut ini penjelasannya dari kedua metode tersebut.
A. Metode Pencarian Beruntun
Metode ini banyak digunakan karena efektif untuk melakukan pencarian dari
sekumpulan data, baik data sudah terurut maupun yang belum terurut atau masih acak. Bila
dibandingkan dengan yang lainnya, metode ini memiliki cara kerja yang relatif mudah untuk
dipahami. Dalam metode ini, data yang dicari akan dibandingkandengan seluruh elemen
array yang ada. Sebagai contoh, apabila kita memiliki array A yang memiliki indeks 1
sampai n dan kita akan mencari nilai x di dalam array tersebut, maka nilai x tersebut akan
dibandingkan dengan nilai A[1] sampai A[n]. Dalam metode ini juga diterapkan bahwa
apabila data ditemukan pada indeks tertentu, maka proses pencarian akan dihentikan. Hal ini
bertujuan agar proses pembandingan nilai tidak dilakukan sampai indeks terakhir karena nilai
yang dicari telah ditemukan.Agar lebih memperjelas, perhatikan gambar proses pencarian
data berikut.
ARRAY A
| |
1
|
75
|
2
|
73
|
3
|
78
|
4
|
81
|
5
|
80
|
Pada gambar di atas, nilai 1, 2, …5 merupakan indeks array sedangkan nilai 75, 73, …
80 merupakan nilai yang terkandung dalam elemen-elemen array. Sekarang misalkan kita
akan melakukan pencarian data 78 di dalam array tersebut, maka salah satu cara yang dapat
digunakan adalah dengan membandingkan nilai 78 tersebut dengan seluruh elemen array
(dari A[1] sampai A[5]). Mula-mula kita akan membandingkan nilai 78 dengan elemen
pertama (A[1]), karena nilainya tidak sama maka pencarian akan dialnjutkan ke elemen
berikutnya (A[2]), begitu seterusnya. Pada saat elemen ketiga, nilai A[3] sama dengan nilai
yang dicari pencarian akan dihentikan.
Berikut ini contoh program yang akan menunjukkan implementasi dari pencarian array
dengan menggunakan metode di atas. Apabila data yang dicari ditemukan dalam array, maka
program akan menampilkan indeks dimana data tersebut berada.
Sekarang tinjaulah kasus apabila ternyata data yang dicari dalam array tidak ditemukan.
Metode ini memiliki kelemahan, yaitu apabila kita memiliki array dengan n buah elemen,
maka dengan metode runtunan ini, program akan melakukan pembandingan nilai sebanyak n
kali, yaitu dari indeks pertama sampai indeks ke-n dan hal ini tidak efisien.
B. Metode Pencarian Bagi Dua
Berbeda dengan metode pencarian beruntun yang dapat digunakan untuk data belum terurut,
metode pencarian bagi dua ini hanya dapat digunakan untuk data-data yang telah terurut, baik
secara menaik maupun menurun.
Setelah data diurutkan, elemen array akan dibagi menjadi dua, sehingga banyaknya proses
pembandingan nilai dapat dikurangi. Sebagai contoh, apabila terdapat array A yang memiliki n
buah elemen dengan indeks 1 sampai n dan datanya telah terurut secara menaik, maka array
tersebut akan dibagi dari indeks 1 sampai ke-k dan k+1 sampai ke n dimana k = n + 1 div 2. hal
2 73
3 78
4 81
5 80
tersebut mengakibatkan array A terbagi menjadi dua bagian, yaitu dari A[1] . . A[k] dan A[k+1] .
. A[n], sedangkan A[k] menjadi pembatas antara dua bagian tersebut. Apabila x (nilai yang
dicari) sama dengan nilai A[k] maka hentikan pencarian, sedangkan bila tidak, periksa apakah
nilai A[k] > x ataukah A[k] < x. Bila A[k] lebih besar dari x, maka ulangi metode pencarian
tersebut untuk A[1] sampai A[k]. Sebaliknya, apabila A[k] lebih kecil dari x, maka ulangi
metode pencarian tersebut untuk A[k+1] sampai A[n]. Perhatikan gambar berikut.
80 merupakan nilai yang terkandung dalam elemen-elemen array. Sekarang misalkan kita
akan melakukan pencarian data 78 di dalam array tersebut, maka salah satu cara yang dapat
digunakan adalah dengan membandingkan nilai 78 tersebut dengan seluruh elemen array
(dari A[1] sampai A[5]). Mula-mula kita akan membandingkan nilai 78 dengan elemen
pertama (A[1]), karena nilainya tidak sama maka pencarian akan dialnjutkan ke elemen
berikutnya (A[2]), begitu seterusnya. Pada saat elemen ketiga, nilai A[3] sama dengan nilai
yang dicari pencarian akan dihentikan.
Berikut ini contoh program yang akan menunjukkan implementasi dari pencarian array
dengan menggunakan metode di atas. Apabila data yang dicari ditemukan dalam array, maka
program akan menampilkan indeks dimana data tersebut berada.
Sekarang tinjaulah kasus apabila ternyata data yang dicari dalam array tidak ditemukan.
Metode ini memiliki kelemahan, yaitu apabila kita memiliki array dengan n buah elemen,
maka dengan metode runtunan ini, program akan melakukan pembandingan nilai sebanyak n
kali, yaitu dari indeks pertama sampai indeks ke-n dan hal ini tidak efisien.
B. Metode Pencarian Bagi Dua
Berbeda dengan metode pencarian beruntun yang dapat digunakan untuk data belum terurut,
metode pencarian bagi dua ini hanya dapat digunakan untuk data-data yang telah terurut, baik
secara menaik maupun menurun.
Setelah data diurutkan, elemen array akan dibagi menjadi dua, sehingga banyaknya proses
pembandingan nilai dapat dikurangi. Sebagai contoh, apabila terdapat array A yang memiliki n
buah elemen dengan indeks 1 sampai n dan datanya telah terurut secara menaik, maka array
tersebut akan dibagi dari indeks 1 sampai ke-k dan k+1 sampai ke n dimana k = n + 1 div 2. hal
2 73
3 78
4 81
5 80
tersebut mengakibatkan array A terbagi menjadi dua bagian, yaitu dari A[1] . . A[k] dan A[k+1] .
. A[n], sedangkan A[k] menjadi pembatas antara dua bagian tersebut. Apabila x (nilai yang
dicari) sama dengan nilai A[k] maka hentikan pencarian, sedangkan bila tidak, periksa apakah
nilai A[k] > x ataukah A[k] < x. Bila A[k] lebih besar dari x, maka ulangi metode pencarian
tersebut untuk A[1] sampai A[k]. Sebaliknya, apabila A[k] lebih kecil dari x, maka ulangi
metode pencarian tersebut untuk A[k+1] sampai A[n]. Perhatikan gambar berikut.
Keadaan pertama
Pada gambar di atas, array terdiri dari 14 buah elemen yang sudah terurut secara menaik
dengan indeks 1 sampai 14. Mula-mula (keadaan pertama), array akan dibagi menjadi dua
bagian. Pembatasnya adalah indeks ke-7. Nilai 7 didapat dari (1+14) div 2. Karena nilai pada
indeks ke-7 (nilai 19) lebih kecil dari nilai yang dicari (nilai 22), maka proses pencarian akan
diulang untuk indeks ke-8 sampai ke-14. Pada keadaan kedua ini array tersebut juga akan dibagi
menjadi dua, sehingga pembatasnya adalah indeks ke-11, yang berasal dari (8+4) div 2. Karena
nilai pada indeks ke-11 (nilai 25) lebih besar dari nilai yang dicari (niali 22), maka proses
pencarian akan dilakukan lagi untuk indeks ke-8 sampai ke-10. Pada keadaan ini (keadaan
ketiga), array akan dibagi menjadi dua pada indeks ke-9, yang berasal dari (8+10) div 2. Karena
nilai pada indeks ke-9 sama dengan nilai yang dicari, maka proses pencarian pun dihentikan.
3. Daftar Alat dan Bahan
1. Personal Komputer 1 Unit
2. Software yang sudah ada
4. Keselamatan Kerja
1. Sebelum melakukan langkah percobaan, pastikan kabel power terhubung ke Power
Supply.
2. Matikan komputer setelah praktikum selesai.
5. Langkah Kerja
Buatlah program untuk soal-soal di bawah ini:
1. Mengaplikasikan algoritma runtutan sebuah data array
dengan indeks 1 sampai 14. Mula-mula (keadaan pertama), array akan dibagi menjadi dua
bagian. Pembatasnya adalah indeks ke-7. Nilai 7 didapat dari (1+14) div 2. Karena nilai pada
indeks ke-7 (nilai 19) lebih kecil dari nilai yang dicari (nilai 22), maka proses pencarian akan
diulang untuk indeks ke-8 sampai ke-14. Pada keadaan kedua ini array tersebut juga akan dibagi
menjadi dua, sehingga pembatasnya adalah indeks ke-11, yang berasal dari (8+4) div 2. Karena
nilai pada indeks ke-11 (nilai 25) lebih besar dari nilai yang dicari (niali 22), maka proses
pencarian akan dilakukan lagi untuk indeks ke-8 sampai ke-10. Pada keadaan ini (keadaan
ketiga), array akan dibagi menjadi dua pada indeks ke-9, yang berasal dari (8+10) div 2. Karena
nilai pada indeks ke-9 sama dengan nilai yang dicari, maka proses pencarian pun dihentikan.
3. Daftar Alat dan Bahan
1. Personal Komputer 1 Unit
2. Software yang sudah ada
4. Keselamatan Kerja
1. Sebelum melakukan langkah percobaan, pastikan kabel power terhubung ke Power
Supply.
2. Matikan komputer setelah praktikum selesai.
5. Langkah Kerja
Buatlah program untuk soal-soal di bawah ini:
1. Mengaplikasikan algoritma runtutan sebuah data array
2. Mengaplikasikan algoritma pencarian bagi dua sebuah data array
6. Analisa
1. Pada percobaan ini ada 9 angka acak yaitu 5,6,8,1,10,15,7,4, dan 9 disusun secara ter-urut. Disini kita inputkan angka 15 dan outputnya menampilkan bahwa angka 15 ada pada urutan angka ke-6.
2. Pada percobaan ini kita memasukkan ukuran array berjumlah 6 angka yang dapat di urut, kemudian di inputkan angka sebanyak 6 angka sesuai batas array yang ditentukan. Lalu kita masukkan angka 8 sebagai angka yang dicari dan angka 8 ditemukan pada urutan angka tersebut karena angka empat ada pada urutan array yang di inputkan. Jika angka 8 tidak ada pada array, akan muncul kalimat “Angka tidak ditemukan”.
7. Kesimpulan
Algoritma pencarian merupakan algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi.
0 Comments