TUGAS KELOMPOK PERTEMUAN 11 | LOGIKA DAN ALGORITMA

Nama Kelompok :

1. Kowiyul Iman          : 12201184

2. Agung Prayogi        : 12201104

3. Nurul Hikmah          : 12200357

4. Nabillah Sujaen      : 12201112

5. Maulida Yustikarina   : 12201142

 

Kelas                        : 12.1B.37

PERTEMUAN 11

TEKNIK SEARCHING

 HD

1.     Pengertian Teknik Searching

Teknik dalam memilih dan menyeleksi sebuah elemen dari beberapa elemen yang ada.

2.     Teknik Pencarian (Searching)

A.    Teknik Pencarian Tunggal

1)    Teknik Sequential Search/Linier Search

2)    Teknik Binary Search

 

B.    Teknik Pencarian Nilai MAXMIN

1.       Teknik StraitMAXMIN

2.       Teknik D and C

 

A.  Teknik Pencarian Tunggal

 

1.   Teknik Sequential Search/Linier Search

Linear search adalah algoritma pencarian nilai tertentu pada sebuah array/list. Algoritma pencarian ini melibatkan pemeriksaan nilai elemen pada list satu demi satu dari ujung list. Karena mekanisme kerjanya, algoritma ini juga dikenal juga dengan nama lain sequential search. Algoritma ini cocok digunakan pada array/list dengan nilai yang tidak terurut.

==> Ilustrasi dalam Teknik Sequential Search/Linier Search

 

Misalnya kita memiliki sebuah list, anggap saja list a. Di dalam list itu terdapat beberapa elemen yang terdiri dari beberapa angka acak. Katakanlah 8,5,7,9,2. Kita ingin mencari sebuah angka dari dalam list tersebut, misalnya angka 7. Dan juga kita bisa juga sekaligus mendapatkan informasi pada indeks ke berapa letak angka tersebut berada, berapa kali iterasinya (proses perulangan saat mencari data tersebut).

Algoritma :

1. Tentukan I = 1

2. Ketika Nilai (I) <> X Maka Tambahkan I = I +1

3. Ulangi langkah No. 2 sampai Nilai(I) = X

4.Jika Nilai (I) = N+1 Maka Cetak “Pencarian Gagal” selain itu Cetak “ Pencarian Sukses “

Contoh 1 :

Data A = { 8,5,7,9,2}

Dicari 9

 

Langkah pencariannnya:

Langkah 1 : A[1] = 9

Langkah 2 : 8 <> 9, maka A[2] = 5

Langkah 3 : ulangi langkah 2

Langkah 2 : 5 <> 9, maka A[3] = 7

Langkah 2 : 7<> 9, maka A[4] = 9

Langkah 2 : 15 = 15

Langkah 4 : “Pencarian Sukses”

 

Contoh 2 :

Diberikan Larik(L) dengan n=6 elemen

Data dari Larik L adalah sebagai berikut:

11

16

9

23

28

12

 

Misalkan data yang dicari adalah x = 12

• data X = 12 akan dibandingkan dengan ke I=1 sampai I =6

 

Langkah Pencariannya :

Langkah 1 :

1. i=1 → data = 11, X=12

2. Bandingkan 11 <> 12, tambahkan I = I +1

 

Langkah 2 :

1. I = 2 → data = 16, X=12

2. Bandingkan 16 <> 12, tambahkan I = I +1

 

Langkah 3 :

1. i=3 → data = 11, X=12

2. Bandingkan 9 <> 12, tambahkan I = I +1

 

 

Langkah 4 :

1. i=4 → data = 23, X=12

2. Bandingkan 23 <> 12, tambahkan I = I +1

Langkah 5 :

1. i=5 → data = 28, X=12

2. Bandingkan 28 <> 12, tambahkan I = I +1

Langkah 6 :

1. i=6 → data = 12, X=12

2. Bandingkan 12 = 12, maka data berhasil ditemukan.

3. Indeks yang dicari ditampilkan yaitu 6

 

Contoh 3 :

Apabila ditemukan kondis i:

Nilai (i) = N + 1, maka pencarian tidak ditemukan atau gagal.

Dikarenakan jumlah elemen adalah N, N + 1 artinya data yang dicari bukan merupakan elemen data dari N.

 

2.   Teknik Binary Search

Binary Search merupakan metode pencarian data dengan membagi 2 atau pencarian  dimulai dari indekslist bagian tengah, lalu membandingkannya. Jika bertemu dengan angka yang lebih kecil dari pada yang dicari, maka langsung dibuangnya, begitu seterusnya hingga nilai yang dicari (==)  cocok.  Untuk lebih jelasnya, perhatikan gambar animasi di bawah ini.

Perlu diketahui, data list pada binary search sangatlah mengharuskan urut terlebih dahulu sebelum memulai proses pencarian. Secara logaritmik pencarian binary lebih cepat dibandingkan linear search karena dapat mereduksi jumlah elemen yang dicari sehingga iterasi yang dihasilkannya lebih sedikit.

 

Algoritma Binary Search :

Binary Search (Lanjutan)

1. Low = 1 , High = N

2. Ketika Low <= High Maka kerjakan langkah No .3, Jika tidak Maka kerjakan langkah No.7

3. Tentukan Nilai Tengah dengan rumus

(Low + High) Div 2

4. Jika X < Nilai Tengah, Maka High = Mid –1, Ulangi langkah 1

5. Jika X > Nilai Tengah, Maka Low = Mid +1, Ulangi langkah 1

6. Jika X = Nilai Tengah, Maka Nilai Tengah = Nilai yang dicari

7. Jika X > High Maka Pencarian GAGAL

 

Contoh :

Data A = { 1, 5, 11, 17, 21, 23, 25, 34, 42 }

Dicari 5

 

Langkah Pencariannya:

Langkah 1 : Low = 1 dan High = 11

Langkah 2 : Low <= High (jika YA ke L-3, jika TDK ke L-7)

Langkah 3 : Mid = (1+10) div 2 = 5 yaitu 21

Langkah 4 : 5 < 21, maka High = 5 – 1 = 4 yaitu 11

Langkah 1 : Low = 1 dan High = 4

Langkah 2 : Low <= High

Langkah 3 : Mid = (1+4) div 2 = 2 yaitu 3

Langkah 4 : 3 < 3, ke langkah 5

Langkah 5 : 3 > 3, ke langkah 6

Langkah 6 : 3 = 3 (Pencarian berhasil)

 

B.    Teknik Pencarian Nilai MAXMIN

 

1.    Teknik Strait maksmin adalah teknik pencarian untuk mencari data atau nilai yang lebih besar atau lebih kecil dari data yang lain dari kumpulan data biasanya berbentuk array linier.

 

                                    I.    PENJELASAN SEARCHING STRAIT MAXIMUM :

Untuk menjelaskan proses pencarian data terbesar atau data maksimum dari sekelompok data, di bawah ini akan diberikan contohnya terlebih dahulu.Jika diketahui sebuah sebuah larik data atau vector A yang memiliki 6 elemen data,sebagai berikut:

 

A : 50 20 43 15 66 55

 

Untuk menemukan data maksimum dari vector A, dapat dilakukan dengan cara sebagai berikut. Mula-mula elemen pertama dalam A, yaitu 50 di anggap sebagai data maksimum. Selanjutnya 50 kita bandingkan dengan elemen data yang kedua, yaitu 20. Karena 50 lebih besar dari 20, maka data maksimumnya tetap, yaitu 50. Selanjutnya, 50 kita bandingkan dengan elemen data yang ketiga yaitu 43. Harga data maksimum sebelumnya adalah lebih besar dari 43, sehingga data maksimumnya masih tetap, yaitu 50. Proses dilanjutkan untuk membandingkan kembali data maksimum sementara dengan data-data pada urutan selanjutnya secara berurutan hingga data pada urutan akhir. Ketika dibandingkan dengan data urutan yang ke-5, yaitu 66, ternyata 50 lebih kecil dari 66. Pada akhirnya setelah dibandingkan dengan keseluruhan data dalam vector A, data 66 merupakan data terbesar atau maksimum.

 

                                   II.    PENJELASAN SEARCHING STRAIT MINIMUM :

Pada kasus yang lain, jika diinginkan mencari data terkecil atau data minimum dari sekelompok data pada dasarnya langkah-langkah yang dilakukan adalah sama dengan algoritma prosedur pencarian data maksimum sebagaiman dijelaskan sebelumnya. Perbedaannya adalah terletak pada langkah ke-4, yaitu pertukaran data akan dilakukan jika data pada ukuran berikutnya memiliki harga yang lebih rendah dari nilai sebelumnya. Pada vector A dalam contoh sebelumnya, nilai 15 adalah merupakan data minimum atau terkecil dari semua data pada vector A.

 

Waktu tempuh/time complexity yang digunakan untuk menyelesaikan pencarian hingga mendapatkan solusi yang optimal terbagi atas :

– Best Case

– Average Case

– Worst Case

 

BEST CASE

Keadaan yang tercapai jika elemen pada himpunan A disusun secara increasing (menaik). Dengan perbandingan waktu n-1 kali satuan operasi.

 

CONTOH KASUS BEST CASE :

Pada Himpunan A yang berisi {5,-4,9,7} dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.

Penyelesaian :

Elemen Max = 9, dan elemen min = -4

Jumlah operasi perbandingan adalah (3 *4/2-1)=5 kali satuan operasi

 

Tentukan atau cari bilangan Max & Min serta jumlah operai perbandingan yang dilakukan.

 

Penyelesian :

Untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN yang menghasilkan bilangan min = 3 bilangan max = 15, operasi perbandingan mencari bilangan MaxMin dari himpunan tersebut adalah (n-1) = 4 kali operasi.

 

AVERAGE CASE

Jika pencarian elemen MaxMin dilakukan pada elemen dalam himpunan yang tersusun secara acak ( tidak decreasing / tidak increasing ) jumlah operasi. Perbandingan yang dilakukan adalah rata – rata waktu tempuh best case dan worst case yaitu ½[(n-1) + 2(n-1)]=(3n/2 – 1)kali

 

Contoh Kasus Average Case :

Pada Himpunan A(1) = 15, A(2) = 7, A(3) = 11, A(4) = 3, A(5) = 5,A(6) = -2 dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.

 

Penyelesaian :

Elemen Max = 15, dan elemen min = -2 Jumlah operasi perbandingan adalah (3 (6/2)-1)=8 kali satuan operasi.

 

WORST CASE

Terjadi jika elemen dalam himpunan disusun secara decreasing ( menurun ). Dengan Operasi perbandingan sebanyak 2 ( n-1) kali satuan operasi.

 

Contoh Kasus Worst Case :

Cari elemen MaxMin dan jumlah Operasi perbandingan yang dilakukan terhadap himpunan A yang disusun decreasing. A(1) = 15, A(2) = 11, A(3) = 7, A(4) = 5, A(5) = 3.

 

Penyelesaian :

untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN adalah elemen max = 15 dan elemen min = 3, operasi perbandingan untuk elemen MaxMin tersebut adalah 2(5-1) = 8 kali satuan operasi.