CATATAN ILMU

Teknik Pencarian :

1. Teknik Pencarian Tunggal :
      - Teknik Sequential Search / Linier Search
      - Teknik Binary Search

2. Teknik Pencarian Nilai MAXMIN :
      - Teknik Strait MAXMIN
      - Teknik D and C

1. Teknik Pencarian Tunggal

     A. Teknik Sequential Search / Linier Search
          Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan kebelakang atau dari awal sampai akhir, dalam artian pencarian dimulai dari record ke-1 diteruskan ke record selanjutnya secara berurutan yaitu record-2,record-3, dst, sampai ditemukan isi record yang sama dengan informasi yang dicari. Kelebihannya adalah apabila data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Namun apabila data yang diperlukan terletak diakhir maka akan membutuhkan waktu yang agak lama untuk menemukannya.

Algoritma/Caranya :
1. Tentukan urutan data/ nilai I = 1
2. Ketika urutan data/ nilai I bukanlah data yang dicari (I<>X) maka tambahkan nilai 1 pada I(I = I+1)
3. Ulangi langkah No.2 sampai data yang dicari ditemukan ( I=X)
4. Jika urutan melebihi data yang ada atau dengan kata lain dari seluruh jumlah data yang ada masih belum menemukan hasil  (I= N+1), Maka Pencarian dikatakan gagal.

     B. Teknik Binary Search
             Binary Search adalah algoritma pencarian untuk data yang telah terurut, yaitu data yang diurutkan dari yang besar ke kecil ataupun sebaliknya, pencarian dilakukan dengan langsung menebak apakah data yang dicari berada ditengah-tengah data yang lainnya, kemudian membandingankan data yang ditengah dengan data yang dicari, apabila sama maka dapat dikatakan data ditemukan, namun apabila data yang dicari ternyata lebih kecil daripada elemen tengah, maka pencarian dilakukan dari bagian tengah ke bawah.

Algoritma/Caranya :
1. Anggap saja Urutan Terendah (UR) = 1, Urutan Tertinggi (UT)  = N (nilai belum diketahui, bisa 10,100, atau 1000).
2. Ketika Urutam Tertinggi (UT) tidak lebih besar daripada Urutan Terendah (UR), maka kerjakan ke no.3, jika tidak, dengan kata lain data yang dicari dibawah Urutan Terendah (UR), maka kerjakan no.7
3. Tentukan nilai tengah denga rumus = (Urutan Terendah (UR) + Urutan Tertinggi (UT))/2
4. Jika data yang dicari < daripada Nilai Tengah maka Nilai Tengah mundur -1 ke arah UR
5. Jika data yang dicari > daripada Nilai Tengah maka Nilai Tengah maju + 1 ke arah UT
6. Jika data yang dicari = nilai tengah, maka pencarian langsung ketemu.
7. Jika data yang dicari > daripada Urutan Tertinggi (UT), maka Pencarian gagal

2. Teknik Pencarian Nilai MAXMIN


     A. Teknik Strait MAXMIN
            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.

1.    PENJELASAN SEARCHING STRAIT MAKSIMUM
       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.
 
2.   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 :
Terdapat himpunan A yang berisi 5 buah bilangan telah disusun secara increasing A = 3,5,7,11,15. Dengan 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
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
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 :
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.

     B. Teknik Dengan Teknik D AND C
Contoh :
Tentukan elemen MAXMIN suatu array A yang terdiri 9 bil :

A(1) =22
A(2) =13
A(3) =-5
A(4) =-8
A(5) =15
A(6) =60
A(7) =17
A(8) =31
A(9) =47