SEARCH ( PENCARIAN )

 Pencarian Pengertian

Searching merupakan kegiatan mencari data yang akan dibutuhkan. Searching dalam pemrograman dapat dilakukan untuk mencari data yang berada pada memori komputer. Dalam kehidupan sehari-hari kita sering melakukan Searching seperti pada saat mencari data maupun informasi yang ada di internet. Terdapat macam-macam metode yang dapat digunakan dalam Searching , dan lain-lain :

·        Pencarian Berurutan 

·        Pencarian Biner 

1.         Pencarian Berurutan

Sequential Search adalah sebuah metode pencarian data dalam array dengan cara membandingkan data yang akan dicari dengan data yang terdapat dalam array secara berurutan. Pencarian data dengan menggunakan metode Sequential Search lebih efektif untuk mencari data dalam posisi tidak terurut atau acak.

Proses Pencarian Berurutan dapat dijelaskan sebagai berikut :

1.        Menentukan data yang akan dicari .

2.        Membaca susunan data satu per satu secaras ekuensial

3.        Membaca data dimulai dari data pertama sampai dengan data terakhir, kemudian data yang dicari akan dibandingkan dengan masing-masing data yang terdapat dalam array .

A.       Apabila data yang dicari ditemukan maka kita dapat membuat pernyataan bahwa data telah ditemukan.

B.      Jika data yang dicari tidak ditemukan maka kita dapat membuat pernyataan bahwa data tidak ditemukan.

 Ilustrasi:

Data yang dicari yaitu 7 , lalu disimpan dalam variabel x, kemudian akan dibandingkan dengan satu per satu secara kuensial terhadap data yang terdapat dalam array . Jika ditemukan data pada array yang sama dengan data yang dicari maka data ditemukan.

Kelebihan dan Kekurangan Sequential Searching yaitu:

·           Kelebihan Sequential Searching adalah Sequential Searching lebih mudah dalam proses implementasi dalam pemrograman.

·           Kekurangan Sequential Searching adalah data yang terdapat dalam suatu array dengan jumlah yang sangat banyak, maka waktu yang diperlukan dalam membandingkan data yang dicari dengan jumlah data dalam suatu array memerlukan waktu yang lebih lama .

Salah Satu Contoh S tudi K asus:

Menemukan data yang akan dicari dalam sebuah array 1 dimensi dimana di dalamnya terdapat data dengan menggunakan metode Sequential Searching . Jika data yang akan dicari dalam array ditemukan, kemudian ditampilkan letaknya dari indexnya.

Pemrograman Sequential Searching sebagai berikut:

 

2.         Pencarian Biner

Metode Binary Search adalah suatu metode pencarian data dengan cara mengelompokkan array menjadi bagian-bagian. Pencarian Biner hanya dapat diterapkan pada data yang telah terurut baik ascending maupun descending dalam suatu array .   

Proses Pencarian Biner dengan data ascending dan telah berurutan :

1.        Mem buat perulangan kemudian tentukan posisi low yaitu yang menandakan indeks paling rendah kemudian tentukan posisi high , setelah itu mencari posisi mid atau tengah = ( high + low )/2

2.        Membandingkan data yang dicari dengan nilai yang berada di posisi tengah atau tengah .

3.        Jika data yang dicari sama dengan nilai yang ada pada posisi tengah atau tengah berarti data ditemukan.

4.        Jika data yang dicari lebih kecil dari nilai yang terdapat pada mid maka pencarian data akan dilakukan dibagian kiri mid dengan melakukan pembandingan. Dengan kondisiposisi high berubah yaitu ( mid - 1) dan posisi low tetap.

5.        Jika data yang dicari lebih besar dari nilai yang terdapat pada mid   maka pencarian data akan dilakukan di bagian kanan dari mid dengan posisi low yang berubah yaitu ( mid + 1) dan posisi high tetap.

Ilustrasi:

Setelah menentukan low dan high lalu menentukan mid . perhitungan mid = ( low + high )/2 jadi mid = (0+4)/2, artinya mid berada pada data ( 2 ) . Data yang dicari kemudian ditempatkan pada variabel x lalu dibandingkan dengan data atau nilai yang berada di tengah . data yang dicari ad alah 7<10 kemudian pencarian data dilakukan pada bagian kiri tengah .

Pencarian di bagian kiri mid masih dalam perulangan yang sama, namun indeksnya dipersempit. Karena data yang dicari lebih kecil dari data pertengahan yang sebelumnya maka posisi tinggi akan berubah yaitu ( pertengahan - 1) yang sebelumnya dan rendah tetap pada posisi yang sama. Kemudian tentukan mid =(0+1)/2 = 0 artinya mid sekarang terletak di data ( 0 ) . lalu data yang dicari dibandingkan dengan pertengahan . 7=7 artinya data telah ditemukan

Kelebihan dan Kekurangan Binary Search :

1.                  Kelebihan Binary Search adalah tidak perlu membandingkan data yang dicari dengan seluruh array data yang ada, hanya cukup melalui titik tengah kemudian kita bias menentukan ke mana selanjutnya mencari data yang akan dicari.

2.                  Kekurangan Binary Search adalah penerapannya agak sedikit lebih rumit di karenakan tidak dapat digunakan pada array data yang masih acak , sehingga harus melakukan sorting terlebih dahulu dalam penerapannya.

Pemrograman Binary Search sebagai berikut:

INTERPOLATION SEARCH

Pencarian interpolasi adalah algoritma pencarian untuk nilai kunci tertentu dalam array terindeks yang telah diurutkan berdasarkan nilai kunci. Pencarian ini juga disebut pencarian ekstrapolasi.

Hal ini berdasarkan pada bagaimana manusia mencari nama tertentu melalui buku telepon.

Kompleksitas waktu kasus rata-rata pencarian interpolasi adalah perbandingan O(logn(logn)), dimana n adalah jumlah elemen yang akan dicari. Dalam kasus terburuk, hal ini dapat menghasilkan perbandingan O(n) yang setara dengan pencarian linier.

Program ini memiliki array input berukuran 10 yang diinisialisasi dengan 10 nilai. Ini mengembalikan indeks elemen, jika ditemukan dan -1 jika tidak menggunakan Algoritma Pencarian Interpolasi.
Berikut adalah kode sumber Program C++ untuk Menerapkan Algoritma Pencarian Interpolasi. Program C++ berhasil dikompilasi dan dijalankan pada g++-4.3.2 pada sistem Linux. Output program juga ditampilkan di bawah ini.

1. //Ini adalah Program C++ untuk mengimplementasikan Algoritma Pencarian Interpolasi.

2. #termasuk <iostream>

3. menggunakan  namespace std ;

5. //Mencetak nilai array

6. batal print_ar ( int ar [ ] , int ukuran )

7. {

8.   untuk  ( int i =  0 ; i < ukuran ;  ++ i )

9.   {

10.     cout  << ar [ saya ]  <<  " " ;

11.   }

12.     cout  << endl ;

13. }

15. //Pencarian Interpolasi

16. int interpolasi_pencarian ( int ar [ ] , nilai int , ukuran int )

17. {

18.   int rendah =  0 ;

19.   int tinggi = ukuran -  1 ;

20.   int tengah ;

22.   sementara  ( ar [ rendah ]  <= nilai dan ar [ tinggi ]  >= nilai )

23.   {

24.     tengah = rendah +  ( ( nilai - ar [ rendah ] )  *  ( tinggi - rendah ) )  /  ( ar [ tinggi ]  - ar [ rendah ] ) ;

25.     jika  ( ar [ pertengahan ]  < nilai )

26.     {

27.       rendah = pertengahan +  1 ;

28.     }

29.     else  if  ( ar [ pertengahan ]  > nilai )

30.     {

31.       rendah = pertengahan -  1 ;

32.     }

33.     kalau tidak

34.     {

35.       kembali pertengahan ;

36.     }

37.   }

39.   jika  ( ar [ rendah ]  == nilai )

40.   {

41.     kembali rendah ;

42.   }

43.   kalau tidak

44.   {

45.     kembali  - 1 ;

46.   }

47. }

49. //Fungsi Pengemudi

50. int utama ( )

51. {

52.   int ar [ ]  =  { 1 , 2 , 78 , 18 , 16 , 30 , 29 , 2 , 0 , 199 } ;

53.   nilai int , pos ;

55.   cout  <<  "Array Anda : " ;

56.   cetak_ar ( ar, 10 ) ;

58.   cout  <<  "Masukkan nilai yang dicari : " ;

59.   cin  >> nilai ;

60.   pos = pencarian_interpolasi ( ar, nilai, 10 ) ;

61.   jika  ( pos ! =  - 1 )

62.   {

63.     cout  <<  "Nilai Ditemukan! pada posisi : "  << pos +  1  << endl ;

64.   }

65.   kalau tidak

66.   {

67.     cout  <<  "Maaf, nilai yang Anda cari tidak ada."  << endl ;

68.   }

70.   kembali  0 ;

71. }

Untuk melakukan pencarian dengan Tipe Data lain, maka tinggal di ubah variabel array A[100] yang sebelumnya tipe integer ke tipe string, terus variabel cari juga di ganti tipe datanya menggunanakan string.

Contoh:

• string cari;

• string A[100];

Jangan lupa include header string nya juga.