SEARCH (PENCARIAN)

- PENGERTIAN

Searching merupakan salah satu teknik algoritma yang digunakan untuk mencari suatu data/nilai tertentu didalam memori komputer. Algoritma searching tidak hanya digunakan dibahasa pemrograman C++ namun juga di bahasa yang lain.

Dalam kehidupan sehari-hari, seringkali kita berurusan dengan pencarian misalnya untuk mencari istilah dalam kamus. Pada aplikasi komputer, pencarian kerapkali dilakukan misalnya untuk proses penghapusan data/record atau mengubah data/record tertentu di dalam suatu tabel atau file, langkah pertama yang harus dilakukan adalah mencari apakah data tersebut terdapat di dalam tabel/file atau tidak. Jika ada maka dapat dihapus atau diubah.

                                                   -KEGUNAAN DATA

Kegunaan beberapa struktur data dalam penyimpanan

data sehingga dapat memudahkan proses pencarian,

tergantung pada:

1.Media penyimpanan data (memori, disk, tape).

2.Karakteristik jenis data yang disimpan (data

numerik/character/string).

3.Jumlah data yang akan disimpan dan keperluan untuk

akses data secepat-cepatnya.

-LINGKUP PENCARIAN

Pencarian dapat dilakukan berdasarkan tempat penyimpanan, yang dibagi atas dua, yaitu pencarian internal dan pencarian eksternal. Pencarian internal yaitu pencarian yang dilakukan terhadap data yang berada dalam memori komputer. Pencarian eksternal yaitu pencarian yang dilakukan terhadap data yang berada dalam memori eksternal. Di dalam pembahasan ini hanya membahas tentang pencarian internal.

Pada umumnya dikenal tiga metode searching, antara lain:

Sequensial Search, Binary Search, dan Interpolation Search.

                                              -SEQUENTIAL SEARCH

Sequential Search (pencarian beruntun) adalah metode

pencarian yang paling mudah. Prosesnya membandingkan

setiap elemen array satu-per-satu secara beruntun yang

dimulai dari elemen pertama hingga elemen yang dicari

ditemukan atau hingga elemen terakhir dari array.

Pencarian beruntun dapat dilakukan terhadap elemen

array yang belum terurut atau terhadap elemen array yang

terurut. Perbedaan dari keduanya terletak pada efisiensi

operasi pembandingan yang dilakukan.

Dengan kata lain sequential search akan mencari data dengan cara

membandingkannya satu-per-satu dengan data yang ada. Metode ini disarankan

untuk digunakan pada data yang sedikit saja.

-CONTOH PROGRAM SEQUENTIAL SEARCH

-CONTOH PROGRAM SEQUENTIAL SEARCH

-BINARY SEARCH

Binary search adalah metode pencarian suatu data atau elemen di dalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu (menaik atau menurun). Prinsip dari binary search terhadap N elemen dapat dijelaskan

seperti berikut:

•Tentukan posisi awal = 0 dan posisi akhir = N-1.

•Hitung posisi tengah = (posisi awal + posisi akhir)/2.

•Bandingkan data yang dicari dengan elemen posisi tengah.

-CONTOH BINARY SEARCH

Misalkan kita mempunyai sederetan data dalam array nilai sebanyak 10 elemen dan

akan dilakukan pencarian data 87.

•Nilai[0,9] = 12, 45, 23, 87, 90, 55, 15, 25, 40, 21

Urutkan elemen array secara menaik, sehingga diperoleh:

•Nilai[0,9] = 12, 15, 21, 23, 25, 40, 45, 55, 87, 90

•Data yang akan dicari = 87 (Bilangan)

•Tentukan nilai awal = 0, akhir = N-1 = 9

•Hitung tengah = (9+0)/2 = 4

-CONTOH BINARY SEARCH

(1.)Bandingkan Bilangan < Nilai[tengah] → 87=25→false

(2.)Bandingkan Bilangan < Nilai[tengah] → 87<25→false

(3.)Bandingkan Bilangan < Nilai[tengah] → 87>25→true maka pencarian dilakukan ke

(4.)sebelah kanan dengan nilai awal = tengah + 1 = 5

5.Karena awal masih lebih kecil dari akhir maka ulangi kembali mulai menghitung tengah

6.Hitung tengah = (9+5)/2 = 7

7.Bandingkan Bilangan < Nilai[tengah] → 87=55→false

8.Bandingkan Bilangan < Nilai[tengah] → 87<55→false bandingkan Bilangan < Nilai[tengah] → 87>55→true maka pencarian dilakukan kesebelah kanan dengan nilai awal = tengah + 1 =8

 9.Karena awal masih lebih kecil dari akhir maka ulangi kembali mulai menghitung tengah,dst.

-CONTOH PROGRAM BINARY SEARCH

                -INTERPOLATION SEARCH

Proses pencarian data ini hampir sama dengan proses

pencarian binary search. Pencarian ini juga dilakukan pada

kumpulan data yang sudah urut (menaik atau menurun). Akan

tetapi jika pada binary search kita membagi data dengan

(akhir+awal)/2 tiap prosesnya, maka pada interpolation search

kita akan membagi data menurut rumus sebagai berikut:

Posisi =

(kunci – data[low]/data[high] – data[low]) * (high – low) + low

-CONTOH PROGRAM INTERPOLATION SEARCH