Wednesday, March 13, 2013

Algoritma Metode Pencarian Biner

Metode Biner
Metode ini memerlukan syarat bahwa data hanya bisa dicari pada sekumpulan data yang terurut. Oleh karena itu, sebelum dilakukan pencarian, data sudah harus dalam keadaan terurut.
Dalam algoritma ini, setelah user melakukan pengisian n buah data, data kemudian diurutkan dengan menggunakan metode bubble (gelembung) secara ascending (dari kecil ke besar). Mengenai metode pengurutan akan dibahas secara tersendiri dalam sub bab berikutnya.
Perlu diketahui bahwa apabila data terurut secara descending (dari besar ke kecil), maka metode perlu dirubah sedikit. Hal ini akan menjadi soal latihan buat anda.
Ide dasarnya adalah seperti seseorang mencari suatu kata dalam kamus. Pertama-tama, orang akan membuka pertengahan dari kamus, kemudian melihat apakah ada kata yang dicari di pertengahan tersebut. Apabila tidak ditemukan, maka orang akan mencari ke belakang, atau ke depan, sesuai dengan kondisi apakah kata yang dicari berada di urutan yang lebih kecil atau yang lebih besar dari kata yang ada di tengah kamus tersebut. Orang tersebut akan mengulangi membuka pertengahan sisanya, kemudian mencari di pertengahan tersebut, dan seterusnya hingga kata ditemukan atau mungkin saja kata tersebut tidak berada dalam kamus tersebut.
Berdasarkan hal di atas, dalam algoritma, kita mendeklarasikan 2 variabel, yaitu awal dan akhir, yang berfungsi sebagai penyimpan indeks batas pencarian, serta sebuah variabel tengah, yang berfungsi sebagai indeks yang hendak dibandingkan dengan data cari.
Langkah-langkah pencariannya adalah sebagai berikut:
Misalkan n adalah banyaknya data, x adalah data yang hendak dicari.
1. Tentukan batas awal dan batas akhir pencarian, yaitu dari data 1 s/d n awal < 1 dan akhir < n
2. Hitung nilai tengah yaitu tengah < (awal + akhir) div 2 Terdapat 3 partisi, yaitu data (awal s/d tengah-1); (tengah); (tengah+1 s/d akhir)
3. Bandingkan x dengan data[tengah]. Bila sama, berarti data ditemukan. Algoritma selesai. Bila x < data[tengah] berarti pencarian dilakukan untuk data awal s/d tengah–1, yaitu batas akhir pencarian diubah menjadi tengah-1 akhir  tengah – 1 Bila x > data[tengah] berarti pencarian dilakukan untuk data tengah+1 s/d akhir, yaitu batas awal pencarian diubah menjadi tengah+1 awal < tengah + 1
4. Ulangi mengerjakan langkah 2 hingga data ditemukan atau batas awal lebih besar dari batas akhir.


01| Algoritma Pencarian_Metode_Biner
02| {Menginputkan n data integer, lalu mengurutkannya menggunakan metode bubble secara ascending. Kemudian algoritma menanyakan user data yang hendak dicari, lalu menerapkan metode biner untuk melakukan pencarian. Bila ditemukan, maka algoritma mencetak posisi indeks data ditemukan}
03| Deklarasi:
04| const max = 50
05| type TData = integer
06| type TLarik = array[1..max] of TData
07| data : TLarik
08| k, n, m : integer
09| x : TData {menyimpan data yang hendak di cari}
10| awal, akhir, tengah : integer {menyimpan indeks}
11| ketemu : boolean
12| temp : TData
13| Deskripsi
14| read(n)
15| for k  1 to n do
16| read(data[k])
17| end for
18| {mengurutkan data secara ascending metode bubble}
19| for k  1 to n-1 do
20| for m  k + 1 to n do
21| if data[m] > data[k] then
22| temp  data[m]
23| data[m]  data[k]
24| data[k]  temp
25| end if
26| end for
27| end for
28| {menanyakan user data yang hendak dicari}
29| read(x)
30| {memberikan nilai awal}
31| ketemu  False
32| awal  1
33| akhir  n
34| {menerapkan langkah 2 hingga 4}
35| repeat
36| tengah  (awal + akhir) div 2
37| if x = data[tengah] then
38| ketemu  True
39| else
40| if x < data[tengah] then
41| akhir  tengah – 1
42| else
43| awal  tengah + 1
44| end if
45| end if
46| until ketemu or (awal > akhir)
47| {mencetak informasi}
48| if ketemu then
49| write(tengah) {mencetak indeks posisi data ditemukan}
50| else
51| write(‘data tidak ditemukan’)
52| end if


1 comment:

Kebahagiaan sejati bukanlah pada saat kita berhasil meraih apa yg kita perjuangkan, melainkan bagaimana kesuksesan kita itu memberi arti atau membahagiakan orang lain.