Ada yang belum pernah searching di google? Pasti anak informatika tidak ada yang tidak pernah searching pada mesin pencari yang satu ini yang sudah menjadi andalan bagi para mahasiswa dalam mencari banyak hal, dari yang penting sampai yang tidak penting. Nah kita juga akan membuat program pencarian juga menggunakan program C++. Postingan kali ini adalah kelanjutan materi tentang array. Apa itu searching? Searching adalah metode pencarian informasi dalam suatu aplikasi menggunakan suatu kunci ( key ). Searching diperlukan untuk mencari informasi khusus dari sekumpulan data yang disimpan dalam sebuah array.
Ok, cukup pengantarnya sekarang kita lanjut ke pembahasannya. Searching pada C++ ada dua metode yang biasa digunakan.
- Metode pencarian beruntun atau sequential search
- Metode pencarian bagi dua atau binary search
Kita bahasa satu per satu, yang pertama adalah Pencarian Beruntun atau Sequential search.
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir. Dan untuk sequential search dibagi menjadi dua macam pula, pencarian dengan data sudah terurut dann pencarian dengan data tidak terurut.
Disini kita selalu menggunakan array, jadi harap diingat bahwa indeks array dimulai dari 0. Jadi posisi atau letak elemen di dalam array akan ditunjukkan dengan indeks. Dan perlu diingat juga array itu menggunakan perulangan, jadi pastikan juga Anda menguasai perulangan atau looping.
Ok, kita langsung ke contoh saja supaya lebih jelas.
Berikut outputnya :
Contoh di atas untuk data yang tidak terurut, untuk data yang terurut data harus diurutkan terlebih dahulu namun algoritma untuk pencariannya tetap sama, membandingkan satu per satu antara data yang di cari dengan elemen pada array.
Metode yang kedua adalah Bagi Dua atau Binary Search.
Untuk metode yang satu ini mempunyai syarat mutlak yaitu data HARUS dalam kondisi sudah terurut. Metode pencarian ini biasa kita terapkan ketika mencari kata dalam kamus atau mencari bab dalam sebuah buku. Untuk mencari kata misalnya, kita tidak mungkin mencarinya dari awal sedangkan kata yang kita cari dimulai dari huruf M, pasti kita akan langsung mulai dari tengah.
Begitu juga dengan algoritma Binary search ini. Berikut ini adalah langkah-langkah atau algoritma dari binary search.
- Mula-mula diambil dari posisi awal=0 dan posisi akhir = n (sesuai indeks).
- Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2
- Kemudian data yang di cari dibandingkan dengan data tengah
- Jika sama, data ditemukan, Proses selesai
- Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1
- Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1
4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
Pencarian biner ini akan berakhir jika data ditemukan dan jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.
Bingung? Ok saya ilustrasikan sekali lagi menggunakan contoh. Perhatikan ilustrasi di bawah ini.
Array X mempunyai 5 elemen seperti di bawah ini.
X[5];
Elemen
|
20
|
30
|
40
|
50
|
60
|
indeks
|
0(ia)
|
1
|
2
|
3
|
4(ib)
|
Missal data yang ingin dicari adalah 40. Maka algoritma pencariannya:
cari=40;
ia=0;
ib=4;
tengah=(ia+ib)/2=(0+4)/2=2
setelah ketemu indeks tengah baru dibandingkan dengan data yang dicari.
X[2]==cari? Jika iya berarti data ditemukan. Sama atau tidak? Ternyata sama, berarti pencarian berhenti karena data sudah ditemukan.
Ket: ia=indeks awal, ib=indeks akhir
Bagaimana? Sudah lebih ada gambaran? Supaya lebih jelas kita langsung ke contoh program saja.
Berikut output jika data yang dicari di temukan.
dan berikut output jika data yang di cari tidak ditemukan
Semoga
postingan kali ini bisa membantu. Sampai ketemu di postingan
selanjutnya. Jangan pernah bosan untuk belajar. Jika ada pertanyaan bisa
di tulis di comment atau hubungi langsung di
Contact Us. Script bisa di download
disini untuk
sequential search dan
disini untuk
binary search.