Tehnik Searching Tugas Logika Algoritma [PDF]

Citation preview

TEHNIK SEARCHING LOGIKA & ALGORITMA



Disusun Oleh : NAMA



NIM



Fajar Tri Hastadi 1170223 Okky Wiranata



1821919



Rizki Pratama



1213223



Anis



812818



Wina



8178128



AMIK BSI PONTIANAK 11.1C.KA



KATA PENGANTAR



Puji syukur kita panjatkan kepada Tuhan Yang Maha Esa yang telah memberikan rahmat serta hidayah-Nya, sehingga penyusunan makalah ini dapat diselesaikan. Tugas ini disusun untuk di ajukan sebagai tugas mata kuliah LOGIKA & ALGORITMA dengan judul “ TEHNIK SEARCHING “. Terima kasih kepada rekan-rekan yang telah membantu tugas ini sehingga dapat diselesaikan tepat pada waktunya. Demikianlah tugas ini disusun semoga bermanfaat, umumnya untuk para pembaca dan khususnya bagi penyusun.



Pontianak, 26 November 2017



Penyusun



DAFTAR ISI



KATA PENGANTAR DAFTAR ISI BAB I PENDAHULUAN 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Tujuan 1.4 Manfaat Penulisan 1.5 Pengertian Searching Linier sequential 1.6 Bagaimana algoritma pencarian berurutan itu dan mengaplikaskannya pada sebuah program. BAB II PEMBAHASAN 2.1 Pengertian Searching 2.2 Jenis Searching 2.3 Contoh Pemograman Searching dalam Algoritma BAB III PENUTUP 3.1 Kesimpulan 3.2 Saran DAFTAR PUSTAKA



BAB I PENDAHULUAN 1.1 Latar Belakang



Dalam ilmu Logika dan Algoritma sering kali menemui masalah tentang bagaimana mendapatkan suatu data dalam kumpulan data. Dalam keperluannya untuk mencari data,



terdapat beragam algoritma pencarian (search algoritma). Algoritma sendiri merupakan algoritma yang menerima sebuah argumen ‘a’ dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci ‘a’. Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memory komputer ataupun yang berada dalam penyimpanan ekternal (hardisk). Pencarian yang dilakukan terhadap data yang berada dalam komputer dikenal dengan pencarian internal sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian eksternal. Pencarian internal meliputi pencarian sekuensial (sequential search) dan pencarian (binary search).



1.2 Rumusan Masalah 1. Apa pengertian searching/pencarian? 2. Apa saja jenis-jenis algoritma pencarian? 3. Bagaimana algoritma dan contoh programnya? 4. Pengertian Searching Linier sequential 5. Bagaimana algoritma pencarian berurutan itu dan mengaplikaskannya pada sebuah program.



1.1 Tujuan Dan Manfaat 1. Untuk mengetahui pengertian searching/pencarian. 2. Untuk mengetahui apa saja jenis-jenis algoritma pencarian. 3. Untuk mengetahui algoritma dan contoh program searching. 4. Mengkaji metode Searching Linier sequential sebagai program dalam menyelesaikan pencarian berurutan. 5. Penggunaan Metode Searching Linier Sequential dalam menyelesaikan masalah-masalah yang ada.



BAB II PEMBAHASAN



2.1. Pengertian Searching



Pencarian (searching) merupakan proses fundamental dalam pengelolaan data. Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan). Search algoritma adalah algoritma yang menerima argument a dan mencoba untuk mencari record yang mana key-nya adalah Algoritma bisa mengembalikan nilai record, atau pointer ke record. Record sendiri adalah tipe data yang terdiri atas kumpulan variabel yang dapat berbeda tipenya. Setiap variabel disebut field. Sequensial Search (penelusuran sequensial) yaitu proses mengunjungi melalui suatu pohon dengan cara setiap simpul di kunjungi hanya satu kali yang disebut tree transversal / kunjungan pohon. Sedangkan Binary Search adalah penelusuran pohon biner dimana data yang dimasukkan atau yang sudah ada diurutkan terlebih dahulu. Data dapat di simpan secara temporer dalam memori utama atau di simpan secara permanen di dalam memori sekunder (tape atau disk). Di dalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array), sedangkan di dalam memori sekunder berupa arsip (file). Aktivitas yang berkaitan dengan pengolahan data ini sering di dahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaaan data tersebut di dalam kumpulannya. Aktivitas yang awal sama juga dilakukan pada proses penambahan (insert) data yang baru. Proses penambahan data dimulai dengan mencari apakah data yang ditambahkan sudah terdapat di dalam kumpulan. Jika sudah dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan. Algoritma pencarian yang akan dibicarakan dimulai dengan algoritma pencarian yang paling sederhana yaitu pencarian beruntun atau Sequential Search sampai pada algoritma pencarian yang lebih maju yaitu pencarian bagi dua (Binary Search).



2.2. Jenis-jenis Searching A. Sequential search Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal). Sedangkan kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal). Sequential search memiliki proses sebagai berikut: »



Tentukan banyaknya data yang akan di olah, misal banyak data adalah N.



»



Tentukan data apa yang akan dicari, misal data yang akan dicari adalah C.



» Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K. »



Inisialisasikan K =0



»



Lakukanlah perulangan sebanyak N kali



» Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang diolah sama dengan data yang dicari. »



Jika ternyata sama K=K+1



»



Jika tidak, lanjutkan proses perulangan .



»



Setelah proses perulangan berhenti, periksalah nilai K.



» Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan tampilkan nilai K ke layer sebagai jumlah data yang ditemukan. » Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan »



Proses selesai.



Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika



data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.



Ilustrasi Metode Linier Search : Misalnya terdapat array satu dimensi sebagai berikut: 8 10 12 6 7



1



50



100



     0                1              2             3              4                5                6                   7            index  Value             Kemudian program akan meminta data yang akan dicari, misalnya 6 (x = 6). Iterasi :             6 = 8 (tidak!)             6 = 10 (tidak!)             6 = 6 (Ya!) => output : “Ada” pada index ke-2 Jika sampai data terakhir tidak ditemukan data yang sama maka output : “ data yang dicari tidak ada”.



Best case : jika data yang dicari terletak di depan sehingga waktu yang dibutuhkan minimal. Worst case : jika data yang dicari terletak di akhir sehingga waktu yang dibutuhkan maksimal. Contoh :             DATA = 5 6 9 2 8 1 7 4             bestcase ketika x = 5             worstcase ketika x = 4             *x = key/data yang dicari



B.



Binary Search.



Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan diolah, data yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang akan dicari. Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah terurut.Pengurutan Array bisa menggunakan jenis sorting descending atau asscending.



* Keunggulan Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential search. * Kelemahan Data harus disorting dahulu dan algoritma lebih rumit, tidak baik untuk data berantai.algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun. * Fungsi Pencarian Biner (Binary Search) dilakukan untuk :   



Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulangulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan). Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.



Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : ¤  Data diambil dari posisi 1 sampai posisi akhir N ¤  Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2 ¤  Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar? ¤  Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1 ¤  Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1 ¤  Jika data sama, berarti ketemu.



Untuk lebih jelasnya, perhatikan contoh berikut. Misalkan kita ingin mencari 17 pada sekumpulan data berikut:



1. Mula–mula dicari data tengah, dengan rumus (1+ 9) / 2 = 5.



2. Berarti data tengah adalah data ke-5, yaitu 15. 3. Data yang dicari, yaitu 17, dibandingkan dengan data tengah ini. 4. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1 atau 6.



1. Data tengah yang baru didapat dengan rumus (6 + 9) / 2 = 7. Berarti data tengah yang baru adalah data ke-7, yaitu 23. 2. Data yang dicari, yaitu 17 dibandingkan dengan data tengah ini. 3. Karena 17 < 23, berarti proses dilanjutkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1 atau 6.



1. Data tengah yang baru didapat dengan rumus (6 + 6) / 2 = 6. Berarti data tengah yang baru adalah data ke-6, yaitu 17. 2. Data yang dicari dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada indeks ke-6. 3. Bagaimana jika data yang dicari tidak ada, misalnya 16? 4. Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar dari posisi akhir. 5. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan. Untuk lebih jelasnya perhatikan proses pencarian 16 pada data di atas. Prosesnya hampir sama dengan pencarian 17. Tetapi setelah posisi awal = posisi akhir = 6, proses masih dilanjutkan lagi dengan posisi awal = 6 dan posisi akhir = 5 Disini dapat dilihat bahwa posisi awal lebih besar daripada posisi akhir, yang artinya data tidak ditemukan. Algoritma pencarian biner dapat dituliskan sebagai berikut : 1L←0 2R←N-1 3 ketemu ← false 4 Selama (L Data[m]) maka L ← m + 1 9 Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan  Contoh Studi Kasus Sebuah contoh aksi pencarian biner adalah sebuah permainan tebak-tebakan dimana seorang pemain harus menebak sebuah bilangan bulat positif yang dipilih oleh pemain lain di antara 1 dan N, dengan memanfaatkan jawaban pertanyaan berupa ya dan tidak. Misalnya N adalah 16 dan angka yang dipilih adalah 11, permainan dapat berjalan sebagai berikut:    



Apakah angka lebih besar dari 8? (ya) Apakah angka lebih besar dari 12? (tidak) Apakah angka lebih besar dari 10? (ya) Apakah angka lebih besar dari 11? (tidak)



Sehingga, angka tersebut pasti 11.Pada setiap langkah, kita memilih sebuah angka yang tepat berada di tengah-tengah jangkauan nilai-nilai yang mungkin. Sebagai contoh, saat kita mengetahui angka tersebut lebih besar dari 8, tetapi lebih kecil atau sama dengan 12, kita mengetahui untuk memilih angka di tengah-tengah jangkauan [9, 12] (pada kasus ini 10 adalah yang optimal).



 Program : #include #include



int binary_s(int array[], int size, int elemen); int main() {            int size=10;     int data[10]={2, 3, 5, 6, 12, 44, 56, 65, 73 ,81} ;     cout