BAB 4 SEARCHING (PENCARIAN)Operasi pencarian adalah operasi untuk menemukan sebuah nilai (data) di dalam sekumpulan nilai yang bertipe sama. Untuk menemukan nilai yang kita cari, instruksi yang paling penting yang harus dilakukan adalah memeriksa jika nilai yang kita cari sama dengan salah satu nilai dalam kumpulan nilai yang dimaksud. Metode pencarian yang bisa kita pergunakan tergantung dari:

a. Bagaimana urutan nilai-nilai di dalam kumpulan nilai.

b. Bagaimana struktur data yang dipergunakan untuk menyusun nilai-nilai tersebut.

Kita dapat mempergunakan metode pencarian beruntun atau linear (sequential search atau linear search) jika:

a. Nilai-nilai tersebut belum berurutan.

b. Nilai-nilai tersebut sudah berurutan, tetapi struktur data yang dipergunakan untuk menyimpan nilai-nilai tersebut adalah senarai berkait (linked list, akan dibahas dalam kuliah-kuliah mendatang).

Kita dapat mempergunakan baik metode pencarian beruntun (sequential) maupun metode pencarian biner (binary search), jika:

a. Nilai-nilai tersebut sudah tersusun secara berurutan, danb. Nilai-nilai tersebut disusun ke dalam bentuk larik (array) atau struktur data sejenis yang masing-masing nilai tersimpan dalam bagian-bagian yang mempunyai indeks yang unik dan indeksnya berurutan dari yang paling kecil hingga yang paling besar (bersifat ordinal).

1. Pencarian Beruntun (Sequential Search)

Merupakan algoritma pencarian yang sangat sederhana.

Proses pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan dan seluruh elemen sudah diperiksa.

131614217621

Nilai yang dicari: 21

Maka elemen yang diperiksa : 13 16 14 21

Index ketemu : 4

Nilai yang dicari: 13

Maka elemen yang diperiksa : 13

Index ketemu : 1

Nilai yang dicari: 15

Maka elemen yang diperiksa : 13 16 14 21 76 21

Index ketemu : 0

Algoritma dari proses Pencarian diatas adalah:

1. Tentukan i=1, Ketemu = 0.

2. Masukan Nilai X ( nilai yang dicari.

3. Jika Nilai[i] X maka i=i+1, kembali kelangkah 2.

4. Jika Nilai[i] = X maka Ketemu =i.

5. Jika Ketemu = 0 maka Cetak nilai X tidak ketemu

6. Jika tidak (Ketemu 0)Cetak nilai X ketemu pada posisi Ketemu

7. Selesai

2. Pencarian Biner (Binary Search) atau Pencarian Bagidua.

Jika data yang kita miliki sudah berurutan, kita dapat melakukan proses pencarian dengan metode binary search. Salah satu bentuk pencarian biner adalah metode pencarian yang kita pergunakan dalam kehidupan sehari-hari ketika kita mencari nomor halaman tertentu dari sebuah buku teks. Untuk mencari nomor halaman tersebut, kita tidak melakukan proses pencarian secara beruntun dari halaman pertama sampai dengan halaman terakhir, tetapi kita membagi buku tersebut menjadi 2 bagian (yang mungkin tidak sama besar) dan kemudian menentukan apakah halaman yang kita cari berada pada paruh pertama atau paruh kedua atau tepat pada halaman yang kita bagi. Jika halaman belum ditemukan, kita mengabaikan salah satu paruh buku yang tidak mungkin mengandung halaman yang kita cari dan mengulangi proses pembagian terhadap salah satu paruh buku yang lain, dan kembali memeriksa jika yang dicari berada dalam paruh pertama atau kedua atau justeru tepat pada halaman yang kita bagi. Proses pembagian terus dilakukan sampai kita menemukan nomor halaman yang dicari. Pencarian Biner (Binary Search) dilakukan untuk :

memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Algoritma Searching Biner terurut menaik.Kamus

Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }

Type A = array [ 1 ..... N ] of integer

Cari, BatasAtas, BatasBawah, Tengah : Integer

Ketemu : boolean

ALGORITMA

Input (cari) { meminta nilai data yang akan dicari}

BatasAtas ( 1 { indeks array dimulai dari 1 }

BatasBawah ( N

Ketemu ( False

While (BatasAtas < BatasBawah) and (not ketemu) do

Tengah ( (BatasAtas + BatasBawah) div 2

If A [Tengah] = cari then

Ketemu ( true

Else

If ( A [Tengah] < cari ) then { cari di bagian kanan }

BatasAtas ( Tengah + 1

Else

BatasBawah ( Tengah 1 { cari di bagian kiri }

Endif

Endif

EndWhile

If (ketemu) then

Output ( Data berada di index nomor, Tengah )

Else Output ( Data tidak ditemukan )

EndifContoh Nilai-Nilai data yang sudah terurut :

A2581215253757

12335678

Kasus 1 : cari = 12

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4

A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2 : cari = 15

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4

A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5

Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 8) div 2 = 6

A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5

Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 5) div 2 = 5

A [Tengah] = A [5] = 15, berarti setelah loop ketiga, data ditemukan

Kasus 3 : cari = 10

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4

A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3

Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 3) div 2 = 2

A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3

Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (3 + 3) div 2 = 3

A [Tengah] = A [3] = 8, berarti setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

31