1. Pengertian Algoritma Pencarian (searching)
Pencarian(searhing)
merupakan proses yang fundamental dalam pengolahan data. Proses pensarian
adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama
(baik bertipe dasar maupun bertipe bentukan).
Sebuah
algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang
menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk
masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan
solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang
menerima sebuah argumen kunci dan dengan
langkah-langkah tertentu akan mencari rekaman dengan kunci
tersebut. Setelah proses pencarian
dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang
dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).
1.
Macam-macam Algoritma Pencarian (Searching)
1.1 Pencarian
sekuensial (Sequential searching)
·
Pengertian
Pencarian Sekuensial (sequential searching) atau pencarian
berurutan sering disebut pencarian linear merupakan metode pencarian yang
paling sederhana. Pencarian beruntun
adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai
dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen
sudah diperiksa. Pencarian beruntun terbadi dua:
1. Pencarian
beruntun pada larik tidak terurut;
2. Pencarian
beruntun pada larik terurut.
·
Algoritma
Pencarian berurutan menggunakan prinsip sebagai berikut :
1. data
yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai
data tersebut ditemukan atau tidak ditemukan.
2. Pada
dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah
data.
3. Pada
setiap pengulangan, dibandingkan data ke-i dengan yang dicari.
4. Apabila sama, berarti data telah
ditemukan. Sebaliknya apabila sampai
akhir pengulangan tidak ada data yang sama, berarti data tidak ada.
Kelemahan pada kasus yang paling buruk, untuk N elemen data harus
dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat
dituliskan sebagai berikut :
(1) i
← 0
(2) ketemu
← false
(3) Selama
(tidak ketemu) dan (i <= N) kerjakan baris 4
(4) Jika
(Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
(5) Jika
(ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan
·
Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[8] =
{8,10,6,-2,11,7,1,100};
int cari;
int
flag=0;
printf("masukkan
data yang ingin dicari = ");scanf("%d",&cari);
for(int
i=0;i<8;i++){
if(data[i] == cari) flag=1;
}
if(flag==1)
printf("Data ada!\n");
else printf("Data tidak
ada!\n");
getch();
return 1;
}
Dari program diatas, terlihat bahwa dilakukan
perulangan untuk mengakses semua elemen array data satu persatu berdasarkan indeksnya.
Program menggunakan sebuah variabel flag
yang berguna untuk menadai ada atau tidaknya data yang dicari dalam array
data. Hanya bernilai 0 atau 1.
Flag pertama kali diinisialiasasi dengan
nilai 0.
Jika ditemukan, maka flag akan diset
menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
Semua
elemen array data akan dibandingkan satu persatu dengan data yang dicari dan
diinputkan oleh user.
1.1 Pencarian
Beruntun dengan Sentinel
·
Pengertian
Jika pencarian bertujuan untuk menambahkan elemen baru setelah
elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian
beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih
dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut
sentinel.
· Algoritma
Procedure SeqSearchWithSentinel(input L:
LarikInt, input n: integer, input x: integer, output idx: integer)
DEKLARASI
I:
integer
ALGORITMA
L[n+1]
← X {sentinel}
I ← 1
While (L[i] ≠ x) do
I ← i+1
Endwhile
If idx = n+1 then
idx ← -1
else
idx
← 1
endif
·
Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[7] = {3,12,9,-4,21,6};
int cari,i;
printf("masukkan data yang ingin
dicari = ");scanf("%d",&cari);
data[6] = cari;
i=0;
while(data[i] != cari) i++;
if(i<6) printf("Data ada!\n");
else printf("Data tidak ada!\n");
getch;
return 1;
}
1.1 Pencarian
Biner (binary search)
·
Pengertian
Terdapat metode pencarian pada data terurut yang
paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan
untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan
membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam
larik harus sudah terurut.
BST adalah binary tree yang mana
data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di
dalamnya berlaku:
setiap data di subtree kiri < data
root subtree < setiap data di subtree kanan.
class
BinaryNode {
void printInOrder( )
{
if(
left != null )
left.printInOrder( ); // Left
System.out.println(
element ); // Node
if(
right != null )
right.printInOrder( ); // Right
}
}
class
BinaryTree {
public void printInOrder( )
{
if(
root != null )
root.printInOrder(
);
}
}
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :
- mula-mula
diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi
data tengah dengan rumus (posisi awal + posisi akhir) / 2.
- Kemudian data yang dicari dibandingkan dengan data tengah.
- Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
- Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
- Demikian seterusnya sampai data tengah sama dengan yang dicari.
Algoritma pencarian biner dapat dituliskan sebagai berikut :
L ← 0
R ← N - 1
ketemu ← false
Selama (L <= R) dan (tidak ketemu) kerjakan
baris 5 sampai dengan 8
m ← (L +
R) / 2 83
Jika (Data[m] = x) maka ketemu ← true
Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L ← m + 1
Jika
(ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan.
int binary_search(int cari){
int l,r,m;
l = 0;
r =
n-1;
int ktm = 0;
while(l<=r && ktm==0){
m = (l+r)/2;
if(data[m] == cari)
ktm=1;
else if (cari < data[m])
r=m-1;
else l=m+1; {
if(ktm==1) return 1; else return 0;
}
}
}
