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).
Fungsi Algrotima Searching :
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.
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.
Perhatikan array data berikut ini:
0
1
2
3
4
5
6 indeks
3
|
12
|
9
|
-4
|
21
|
6
|
ffea
ffeb
ffec
ffed
ffef
fffa
fffb alamat
- Terdapat 6 buah data dalam array (dari indeks 0 s/d 5) dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)
- Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja. Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.
- 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 bagi dua 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.
- Algoritma
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.
- Contoh
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;
}
}
}
1.1 Interpolation Search
- Pengertian
- Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci Tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.
- Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data. Rumus posisi relatif kunci pencarian dihitung dengan rumus:
Posisi = kunci –
data[low] x (hight – low) + low
Data[hight] – data[low]
Misal terdapat data sebagai berikut:
Kode
|
Judul Buku
|
Pengarang
|
025
|
The C++ Programming
|
James Wood
|
034
|
Mastering Delphi 6
|
Marcopolo
|
041
|
Professional C#
|
Simon Webe
|
056
|
Pure JavaScript v2
|
Michael Bolton
|
063
|
Advanced JSP & Servlet
|
David Dunn
|
072
|
Calculus Make it Easy
|
Gunner Christian
|
088
|
Visual Basic 2005 Express
|
Antonie
|
096
|
Artificial Life : Volume 1 Gloria
|
Virginia
|
Kunci Pencarian ? 088
Low ? 0
High ? 7
Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]
Kunci[6] = kunci pencarian, data ditemukan : Visual Basic
2005
Kunci Pencarian ? 060
Low ? 0
High ? 7
Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]
Kunci[3] < kunci pencarian, maka teruskan
Low = 3 + 1 = 4
High = 7
Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.
Berarti tidak ada kunci 060.
- Contoh Program
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int interpolationsearch(int a[],int low,int high,int x){
int mid;
while(low<=high){
mid=low+(high-low)*((x-a[low])/(a[high]-a[low]));
if(x==a[mid])
return
mid+1;
if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return -1;
}
int main(){
int arr[MAX];
int i,n;
int val,pos;
printf("\nEnter total elements
(n < %d) : ",MAX);
scanf("%d",&n);
printf("Enter %d
Elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
printf("\nLIST :
");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);
printf("\nSearch
For : ");
scanf("%d",&val);
pos=interpolationsearch(&arr[0],0,n,val);
if(pos==-1)
printf("\nElement %d not found\n",val);
else
printf("\nElement %d found at position %d\n",val,pos);
return 0;
}
inilah materi Algoritma Searching (searching algorithm) II, yang materi nya cukup mudah untuk dimengerti untuk di praktekan.
sekian materi tentang Algoritma Searching (searching algorithm) kali ini,
wassalamualaikkum wr.wb
terima kasih...
sumber : darasinta.blogspot.com
sekian materi tentang Algoritma Searching (searching algorithm) kali ini,
wassalamualaikkum wr.wb
terima kasih...
sumber : darasinta.blogspot.com
No comments:
Post a Comment