Searching

Assalamualaikum.Wr.Wb

Hallo kawan, kembali bersama saya lagi dan kesempatan kali ini kita akan membahas mengenai Searching.

Saat ini kita memperlajari beberapa cara yaitu

1. Sequential Search
2. Binary Search

Tahukah kamu apa itu Sequential Search dan Binary Search ?

Sequential search adalah Teknik yang sederhana dan langsung dapat digunakan pada struktur data baik array maupun linked list. Pencarian data dilakukan secara berurutan satu per satu dari data pertama lalu data kedua dan seterusnya sampai yang dicari ditemukan. Sequential search dilakukan pada data yang acak atau tidak berurutan dan menggunakan operator pembanding.

Contoh:

X = 29

100

10

29

Apakah 100 = 29 ?

Jika tidak indeks++

Kita harus mencari mulai data pertama. Apakah 100! = 29 ? jika tidak kita kedata kedua. 

Apakah 10! = 29 ? jika tidak kita kedata berikutnya.

Apakah 29! = 29 ?

Ketemu = 29

Algoritma sequential search

Dari penulisan algoritma tersebut maka untuk mengerjakan contoh soal diatas yaitu:

Indeks = 0
Kriteria = 29

while(29! = 100 [0])
    {
      indeks++
    }
while(29! = 10 [1])
    {
      indeks++
    }
while(29! = 29 [2])
    {
      indeks++
    }

    Ketemu = x [2] );
    Ketemu = 29

Dalam sequential search terdapat kelebihan dan kekurangannya

Best dan Worst Case

Contoh:
Data = 3 6 5 1 7
Best case ketika x = 3
Worst case ketika x = 7

Disimpulkan maka, Best case terjadi jika data yang dicari berada didepan sehingga membutuhkan waktu sebentar atau minimal untuk menemukannya.
Sedangkan Worst case jika data yang dicari berada diakhir sehingga membutuhkan waktu yang banyak atau maksimal untuk menemukannya.

Setelah kita mengetahui sequential search kita akan mempelajari binary search

Binary Search adalah Teknik yang hanya dapat digunakan pada sorted array, yaitu array yang elemen-elemennya telah terurut. Pencarian data dilakukan dengan mencari data yang berada ditengah dulu. Kemudian jika data yang dicari lebih kecil dari data tengah maka memilih data sebelah kiri dan sebaliknya jika data yang dicari lebih besar dari data tengah maka memilih data yang sebelah kanan.

Contoh:

Tapi bagaimana jika datanya genap ?

Dalam binary search jika datanya genap maka cara menentukan data tengah yaitu:
(indeks pertama+indeks terakhir):2

Dalam binary search terdapat kelebihan dan kekurangannya

Best dan Worst Case
Best case jika data yang dicari terletak ditengah.
worst case jika data yang dicari tidak ditemukan.

Contoh:
Data = 5 6 9 2 8 1 7 4 3
Best case ketika x = 8(T(n)=1)
worst case ketika x = 25(T(n)=5 atau n/2)

Setelah kita memperlajari Sequential search dan Binary search kita mencoba menyelesaikan contoh soal sebagai berikut.

1. Bandingkan kecepatan antara sequential search dan binary search.

2.Disertai langkah-langkahnya.

Untuk mengerjakan data = 17
1. Sequential Kriteria = 17

     1. 17! = X[0](16) = Ya = Indeks++
     2. 17! = X[1](17) = Tidak
          Ketemu = X [1]
          Ketemu = 17

2. Binary Kriteria = 17

     1. (0 + 7) : 2 = 3,5 = 3         
          X[3] = 45

     2. X[1] = 17

Untuk mengerjakan data = 23

1. Sequential Kriteria = 23

     1. 23! = X[0](16) = Ya = Indeks++
     2. 23! = X[1](17) = Ya = Indeks++
     3. 23! = X[2](23) = Tidak
          Ketemu = X [2]
          Ketemu = 23

2. Binary Kriteria = 23

     1. (0+7):2 = 3,5 = 3
         X[3] = 45

     2. X[3] = 45

  

     3. X[2] = 23

Untuk mengerjakan data = 78
1. Sequential Kriteria = 78

     1. 78! = X[0](16) = Ya = Indeks++
     2. 78! = X[1](17) = Ya = Indeks++
     3. 78! = X[2](23) = Ya = Indeks++
     4. 78! = X[3](45) = Ya = Indeks++
     5. 78! = X[4](50) = Ya = Indeks++
     6. 78! = X[5](78) = Tidak
          Ketemu = X [5]
          Ketemu = 78

2. Binary Kriteria = 78

     1. (0+7):2 = 3,5 = 3
         X[3] = 45

     2. (4+7):2 = 5,5 = 5

         X[5] = 78

Dari dua cara berikut disimpulkan bahwa binary search adalah cara yang lebih mudah digunakan karena membutuhkan waktu minimal dengan mencari data tengah terlebih dahulu dan jika datanya genap kita dapat menggunakan cara (indeks pertama+indeks terakhir):2 untuk mendapatkan data tengahnya. Tetapi jika menggunakan sequential search dan data yang dicari berada diakhir maka kita harus mencari satu per satu dari awal dan membutuhkan waktu yang maksimal untuk mengerjakannya.

Dari sedikit materi diatas, Semoga bermanfaat.

Wassalamualaikum.Wr.Wb