Searching
Searching
adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat
pencarian data dapat berupa array dalam memori(pencarian internal), bisa juga
pada file pada external storage(pencarian external).
Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search). Pada Kesempatan ini kita hanya akan membahas tentang pencarian internal menggunakan Array dinamis (pointer).
Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search). Pada Kesempatan ini kita hanya akan membahas tentang pencarian internal menggunakan Array dinamis (pointer).
Metode pencarian
dibagi menjadi 2, yaitu:
1.
Metode Pencarian Beruntun:
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir.
Konsep yang digunakan dalam metode ini adalah membandingkan data-data yang ada dalam kumpulan tersebut, mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir.
2.
Metode Pencarian Bagi Dua:
Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0;
Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen.
Metode ini diterapkan pada sekumpulan data yang sudah terurut (menaik atau menurun). Metode ini lebih cepat dibandingkan metode pencarian beruntun. Data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.
Konsep dasar metode ini adalah membagi 2 jumlah elemennya, dan menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari. Jika bernilai sama, maka langsung data yang dicari ditemukan. Jika data di elemen terurut naik, maka jika data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali. Dan demikian sebaliknya untuk data yang terurut menurun. Dalam hal ini tentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen tersebut.
Indeks awal = i, dimana nilai i, pada awalnya bernilai 0;
Indeks akhir = j, dimana nilai j, pada awalnya bernilai sama dengan jumlah elemen.
Algoritma
Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1. Membaca Array data
2. Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3. Menentukan data yang akan dicari
4. Menentukan elemen tengah dari array
5. Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6. Jika elemen tengah tidak sama dengan data yang dicari maka :
a. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1. Membaca Array data
2. Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3. Menentukan data yang akan dicari
4. Menentukan elemen tengah dari array
5. Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6. Jika elemen tengah tidak sama dengan data yang dicari maka :
a. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
1. Sequential Search (Pencarian berurutan)
Adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
Adalah suatu teknik pencarian data dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
Algoritma pencarian berurutan dapat dituliskan sebagai
berikut :
1. i ← 0
2. ditemukan ← false
3. Selama (tidak ditemukan) dan (i <= N) kerjakan baris 4
4. Jika (Data[i] = x) maka ditemukan ← true, jika tidak i ← i + 1
5. Jika (ditemukan) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan
2. ditemukan ← false
3. Selama (tidak ditemukan) dan (i <= N) kerjakan baris 4
4. Jika (Data[i] = x) maka ditemukan ← true, jika tidak i ← i + 1
5. Jika (ditemukan) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan
Di bawah ini merupakan fungsi untuk mencari data menggunakan
pencarian sekuensial.
int SequentialSearch(int x)
{
int i = 0;
bool ditemukan = false;
while ((!ditemukan) && (i < Max))
{
if(Data[i] == x)
ditemukan = true;
else
i++;
}
if(ditemukan)
return i;
else
return -1;
}
{
int i = 0;
bool ditemukan = false;
while ((!ditemukan) && (i < Max))
{
if(Data[i] == x)
ditemukan = true;
else
i++;
}
if(ditemukan)
return i;
else
return -1;
}
Fungsi diatas akan mengembalikan indeks dari data yang
dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan
nilai –1.
Contoh program:
#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};
cout<<"Data : ";
for(i=0;i<20;i++){
cout<<A[i]<<" ";
}
cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
i++;
}
if (A[i]!=c){
cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};
cout<<"Data : ";
for(i=0;i<20;i++){
cout<<A[i]<<" ";
}
cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
i++;
}
if (A[i]!=c){
cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}
2. Binary Search
Salah satu syarat agar binary search dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, binary search tidak dapat dilakukan.
Prinsip dari binary search dapat dijelaskan sebagai berikut :
a.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.
b.Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
c.Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1. Jika data sama, berarti ketemu.
Salah satu syarat agar binary search dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, binary search tidak dapat dilakukan.
Prinsip dari binary search dapat dijelaskan sebagai berikut :
a.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.
b.Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
c.Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1. Jika data sama, berarti ketemu.
Salah satu syarat agar pencarian biner dapat dilakukan
adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum
dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan
sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner. Misalnya
saat ingin mencari suatu kata dalam kamus 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.Untuk lebih jelasnya perhatikan contoh berikut:
Misalnya ingin mencari data 17 pada sekumpulan data berikut
:
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4.
Berarti data tengah adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17,
dibandingkan dengan data tengah ini. Karena 17 > 15, berarti proses
dilanjutkan tetapi kali ini posisi awal dianggap sama dengan posisi tengah + 1
atau 5.
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7.
Berarti data tengah yang baru adalah data ke-7, yaitu 23. Data yang dicari
yaitu 17 dibandingkan dengan data tenah ini. Karena 17 < 23, berarti proses
dilanjukkan tetapi kali ini posisi akhir dianggap sama dengan posisi tengah – 1
atau 6.
Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5.
Berarti data tengah yang baru adalah data ke-5, yaitu 17. data yang dicari
dibandingkan dengan data tengah ini dan ternyata sama. Jadi data ditemukan pada
indeks ke-5. Pencarian biner ini akan berakhir jika data ditemukan atau posisi
awal lebih besar daripada posisi akhir. Jika posisi sudah lebih besar daripada
posisi akhir berarti data tidak ditemukan.
Untuk lebih jelasnya perhatikan contoh pencarian data 16
pada data diatas. Prosesnya hampir sama dengan pencarian data 17. Tetapi
setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan dan 16 < 17,
maka posisi akhir menjadi posisi tengah – 1 atau = 4 sedangkan posisi awal = 5.
Disini dapat dilihat bahwa posisi awal lebih besar daripada
posisi akhir, yang artinya data tidak ditemukan.
Algoritma pencarian biner dapat dituliskan sebagai berikut :
1 L ← 0
2 R ← N - 1
3 ditemukan ← false
4 Selama (L <= R) dan (tidak ditemukan) kerjakan baris 5 sampai dengan 8
5 m ← (L + R) / 2
6 Jika (Data[m] = x) maka ditemukan ← true
7 Jika (x < Data[m]) maka R ← m – 1
8 Jika (x > Data[m]) maka L ← m + 1
9 Jika (ditemukan) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.
2 R ← N - 1
3 ditemukan ← false
4 Selama (L <= R) dan (tidak ditemukan) kerjakan baris 5 sampai dengan 8
5 m ← (L + R) / 2
6 Jika (Data[m] = x) maka ditemukan ← true
7 Jika (x < Data[m]) maka R ← m – 1
8 Jika (x > Data[m]) maka L ← m + 1
9 Jika (ditemukan) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.
Di bawah ini merupakan fungsi untuk mencari data menggunakan
pencarian biner.
int BinarySearch(int x)
{
int L = 0, R = Max-1, m;
bool ditemukan = false;
while((L <= R) && (!ditemukan))
{
m = (L + R) / 2;
if(Data[m] == x)
ditemukan = true;
else if (x < data[m])
R = m - 1;
else
L = m + 1;
}
if(ditemukan)
return m;
else
return -1;
}
{
int L = 0, R = Max-1, m;
bool ditemukan = false;
while((L <= R) && (!ditemukan))
{
m = (L + R) / 2;
if(Data[m] == x)
ditemukan = true;
else if (x < data[m])
R = m - 1;
else
L = m + 1;
}
if(ditemukan)
return m;
else
return -1;
}
Fungsi diatas akan mengembalikan indeks dari data yang
dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan
nilai –1.
Jumlah pembandingan minimum pada pencarian biner
adalah 1 kali, yaitu apabila data yang dicari tepat berada di tengah-tengah.
Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari
menggunakan rumus logaritma, yaitu : C = 2log(N)
Contoh program:
#include <iostream.h>
#include <conio.h>
#include <string.h>
main ()
{
int jd,no,kiri,kanan,center;
char data[20][50],cari[20];
cout<<"\n\t\t
*************************************** \n";
cout<<"\t\t |
\t\t\t\t | \n";
cout<<"\t\t |
\t Proses Pencarian
\t | \n";
cout<<"\t\t | Menggunakan Algoritma
Binary Search | \n";
cout<<"\t\t |
\t\t\t\t | \n";
cout<<"\t\t
*************************************** \n\n\n";
cout<<" Input Jumlah
Data : ";
cin>>jd;
cout<<endl;
for (no=0;no<jd;no++)
{
cout<<"
Input Data Ke-"<<(no+1)<<" : ";
cin>>data[no];
}
cout<<endl;
cout<<" Input Nilai Dicari :
";
cin>>cari;
kiri=0;
kanan=jd-1;
center=(kanan-kiri)/2;
while ((strcmp(data[center],cari)!=0)
&& (kiri>=0)&& (kanan<jd) && (kanan>=kiri))
{
if (strcmp
(cari,data[center])>0)
{
kiri=center+1;
}
else if (strcmp
(cari,data[center])<0)
{
kanan=center-1;
}
center=kiri+(kanan-kiri)/2;
}
cout<<endl;
if (strcmp(data[center],cari)==0)
{
cout<<"
Keterangan : Data
Ditemukan";
}
else
{
cout<<"
Keterangan : Data Tidak
Ditemukan";
}
getch();
}
DAFTAR PUSTAKA:
hendra-ryuka.blogspot.com/2010/05/searching.html
Komentar ini telah dihapus oleh pengarang.
BalasHapusKomentar ini telah dihapus oleh pengarang.
BalasHapusKomentar ini telah dihapus oleh pengarang.
BalasHapusMantap om
BalasHapus