Searching [Struktur Data]

Assalamualaikum Wr.Wb.

Hai teman teman.. lanjut yuk belajarnya

Kali ini aku akan bahas tentang searching. Apasih searching dalam struktur data ini? Nahh bagi yang belum tahu yukk simak baik baik .

Searching adalah merupakan proses pencarian dalam pengolahan data. untuk menemukan nilai (data) pada sekumpulan data yang bertipe sama.

Searching dibagi menjadi 2 yaitu sequential search dan binary search. Kita bahas satu persatu yaa

1.      Sequential search adalah proses pencarian yang dilakukan secara berurut.  Sequential search merupakan teknik yang paling sederhana dan langsung dapat digunakan pada struktur data baik Array maupun liked list. Sequential search ini biasanya dilakukan pada data yang tidak terurut seperti contoh berikut .

Ø Algoritma sequential search

1.      Input X (data yang dicari)

2.      Bandingka X dengan data ke 1-n

3.      Jika ada data yang sama dengan X maka cetak pesan “Ada”

4.      Jika tidak ada data yang sama dengan X maka cetak pesan “Tidak ada”

Misal :

                       

            Kita lihat pada indeks ke-o yaitu 100!=29 , maka kita lanjut pada indeks ke-1. Lalu kita lihat apakah 10=29? Jika tidak langsung kita ke indeks selanjutnya lagi. Dan terlihat 29=29. Jika sudah menemukan data yang kita cari. Kita dapat menulis data seperti ini : “ Ada pada indeks ke 2 “.

            Jika menulis dengan algoritmanya maka:

                        Indeks = 0

                        Kriteria = 29

                        Maka ditulis :

Ø Ilustrasi sequential search

·         Misal terdapat Array satu dimensi

·         Kemudian program akan meminta data yang dicari, misal 6(x-6)

·         Ilustrasi

6 = 8 (tidak!)

6 = 10 (tidak!)

6 = 6 (ya!) -> output : “Ada” pada indeks ke-2

·         Jika sampai data terakhir tidak ditemukan data yang sama maka output : “data yang dicari tidak ada”.

Nah sampai sini sudah paham belum teman teman apa dan bagaimana itu sequential search? Nanti aku akan kasih contoh soalnya yaa. Lanjut kita akan bahas searching yang kedua yaitu Binary search. Disimak yaa..

1.      Binary search adalah pencarian data yang dimulai dari pertengahan data yang telah terurut.

Adapula ketentuannya untuk mempermudah yaitu, Jika kunci pencarian lebih besar dari kunci posisi tengah, maka kita akan mencari data ke sebelah kanan dan sebaliknya jika kunci pencarian lebih besar dari kunci posisi tengah,  maka kita akan mencari data ke sebelah kiri.

Teknik binary seacrh ini hanya dapat digunakan pada sorted Array, yaitu array yang elemennya telah terurut seperti contoh berikut :

Best and Worst case

·        Best case         : jika data yang dicari terletak didepan, sehingga waktu yang dibutuhkan minimal.

·        Worst case      : jika data yang dicari terletak di akhir,  sehingga waktu yang dibutuhkan maksimal.

Contoh : 

Nah disini aku mau beri contoh soal latihan tentang sequensial search dan binary search ya ..

Soal !

Bandingkan kecepatan antara sequensial search dan binary search disertai langkah – langkahnya.

Kita akan mencari data yang telah di blok kuning

1.     Mencari data X = 17

·      Sequential search

1.      Kriteria – 17

17 = 16 (tidak!) indeks ++

17 = 17 (ya!)  Output -> “Ada” pada indeks ke-1.

·      Binary search

                 Mencari rata tengah dengan rumus : (indeks awal + indeks akhir)/2

0 + 7 / 2 = 3,5 = 3 (dibulatkan yg kecil)

          Indeks 3 = 45

Didapat nilai tengahnya 45. Untuk mencari data X = 17 kita berjalan kekiri, karena 17 < 45.

0 + 3 / 2 = 1,5 = 1

                 Indeks 1 = 17

Dan didapat data yang kita cari x = 17 pada indeks ke-1.

Kesimpulan : dari dua cara diatas dapat kita bandingkan bahwa cara sequential search dan binary search sama sama mudahnya karena data yang kita cari berada di depan, sehingga waktu yang kita butuhkan minimal (best case).

2.     Mencari data X = 23

·      Sequential seacrh

1.      Kriteria = 23

23 = 16 (tidak!) indeks ++

23 = 17 (tidak!) indeks ++

23     23 (ya!)  Output -> “Ada” pada indeks ke-2

·      Binary seacrh

Mencari rata tengah dengan rumus : (indeks awal + indeks akhir)/2

Telah didapat nilai tengahnya 45. Untuk mencari data X = 23 kita berjalan kekiri, karena 23 < 45.

Lalu kita mencari rata tengahnya lagi yaitu 17. Dan 23 > 17 jadi kita berjalan ke kanan dan pada indeks kedua di dapat data yang kita cari.

X = 23 “Ada” pada indeks ke-2

Kesimpulan : dari dua cara diatas dapat kita bandingkan bahwa cara  Binary search lebih mudah,  karena data yang kita cari berada di depan, sehingga waktu yang kita butuhkan minimal (best case).

3.       Mencari data X = 78

·      Sequential seacrh

1.      Kriteria = 78

78 = 16 (tidak!) indeks ++

78 = 17 (tidak!) indeks ++

78 = 23 (tidak!) indeks ++

78 = 45 (tidak!) indeks ++

78 = 50 (tidak!) indeks ++

78 = 78 (ya!)  Output -> “Ada” pada indeks ke-5

·      Binary seacrh

Mencari rata tengah dengan rumus : (indeks awal + indeks akhir)/2

Telah didapat nilai tengahnya 45. Untuk mencari data X = 78  kita berjalan kekanan, karena 78 > 45.

Lalu kita mencari nilai tengahnya lagi dengan rumus seperti diatas

4 + 7 / 2 = 5,5 = 5

Nilai tengah = 78 pada indeks ke-5

Di dapat X = 78 pada indeks ke-5

Kesimpulan : dari dua cara diatas dapat kita bandingkan bahwa cara  Binary search lebih mudah, memang lebih rumit sehingga waktu yang kita butuhkan maksimal (worst case).

Saya memiliki contoh program pencarian 20 data yang telah urut  serta menghitung waktu komputasinya.

Search Data

Data Yang Dicari:

Sekian pembahasan materi tentang searching, semoga bermanfaat dan mudah dimengerti ya teman  - teman.

Terimakasih

Wassalamualaikum.Wr.Wb.