SEARCHING
TI Politala Algoritma Pemrograman 2B
Pengertian Searching
Algoritma pencarian (Searching algorithm) adalah
algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah
tertentu akan mencari argumen kunci tersebut pada data yang telah dimiliki.
Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua
kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak
ditemukan (unsuccessful). Ada dua macam teknik pencarian yaitu pencarian sekuensial (sequential
search) dan pencarian biner (binary search). Perbedaan dari dua
teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila
data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian biner
digunakan pada data yang sudah dalam keadaan urut.
Deklarasi Searching
1. Sequential Search (Linier Search)
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 persatu secara beruntun, mulai
dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen
sudah diperiksa.
Teknik pencarian data dari array yang paling mudah adalah dengan
cara sequential search, dimana data
dalam array dibaca 1 demi satu,
diurutkan dari indeks terkecil ke indeks terbesar, maupun sebaliknya. Jika data yang dicari
mempunyai nilai yang sama dengan data yang ada dalam kelompok data, berarti
data telah ditemukan. Tetapi jika data yang dicari tidak ada yang cocok dengan
data-data dalam sekelompok data, berarti data tersebut tidak ada dalam
sekelompok data.
Contoh :
Array :
int A[] = {1,2,3,4,5,6,7,8,9,10} (indeks array pada bahasa C++ dimulai dari indeks
ke 0) jika kita ingin mencari bilangan 6 dalam array tersebut, maka proses yang terjadi kita mencari
a) Dari array indeks
ke-0, yaitu 1, dicocokan dengan bilangan yang akan dicari, jika tidak sama,
maka mencari ke indeks berikutnya
b) Pada array indeks
ke-1, juga bukan bilangan yang dicari, maka kita mencari lagi pada indeks
berikutnya
c) Pada array indeks
ke-2, ternyata bilangan yang kita cari ada ditemukan, maka kita keluar dari
looping pencarian.
Contoh program sequential
search (Linier Search) :
#include
<iostream>
#include
<conio.h>
using
namespace std;
int
main()
{
int
A[]={1,2,3,4,5,6,7,8,9,10};
int
i, ketemu = 0, n;
int cari;
n = sizeof(A)/sizeof(A[0]);
cout<<"Masukkan data yang dicari :
";cin>>cari;
for(i=0; i<n;i++)
{
if (A[i]==cari)
{
ketemu=!ketemu;
break;
}
}
if(ketemu>0)
{
cout<<"Data ditemukan di posisi:
"<<i+1;
}
else
{
cout<<"Data tidak ditemukan";
}
getch();
}
Hasil running :
2. Binary Search
Binary search merupakan salah satu algoritma untuk melalukan pencarian
pada array yang sudah terurut. Jika
kita tidak mengetahui informasi bagaimana integer
dalam array, maka penggunaan binary search akan menjadi tidak
efisien, kita harus melakukan sorting
terlebih dahulu atau menggunakan metode lain yaitu linear search. Namun jika kita telah mengetahui integer dalam array terorganisasi baik secara menaik atau menurun, maka bisa
dengan cepat menggunakan algoritma binary
search. Adapun ide dasar binary
search yaitu memulai pencarian dengan membagi dua ruang pencarian. Misalnya
kita memiliki array A, dan kita ingin
menemukan lokasi dari spesifik target integer
K dalam array. Ada 3 kemungkinan
kondisi pada binary search yaitu:
1. Jika data target K langsung di temukan, maka proses pembagian
ruangan berhenti. Kemudian print out
indeks data elemen pada array.
2. Jika data target K < A[middle], maka pencarian dapat
dibatasi hanya dengan melakukan pencarian pada sisi kiri array dari A[middle].
Seluruh elemen yang berada di sebelah kanan dapat di abaikan.
3. Jika data target K > A[middle], maka akan lebih cepat jika
pencarian di batasi hanya pada bagian sebelah kanan saja.
4. Jika seluruh data telah di cari namun tidak ada, maka diberi
nilai seperti -1.
Dibawah ini merupakan salah
satu versi program binary search :
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
const int Ar[10]
= {1,2,3,4,5,6,7,8,9,10}; // untuk proses ascending
int tar;
cout<<"masukan data yang dicari : "; cin>>tar;
int awal=0,
akhir=10, tengah;
while (awal
<= akhir)
{
tengah =
(awal + akhir)/2;
if (tar
> Ar[tengah] ) // descending ubah
tanda > menjadi <
{
awal = tengah + 1;
}
else if
(tar < Ar[tengah]) // descending ubah tanda < menjadi >
{
akhir= tengah - 1;
}
else
{
awal = akhir +1;
}
}
if (tar ==
Ar[tengah])
{
cout<<" Data
"<<tar<<" ditemukan, pada posisi ke-
"<<tengah+1<<endl;
}
else
{
cout<<"Data
"<<tar<<" tidak ditemukan "<<endl;
}
getch();
}
Contoh Program Binary Search Lainnya
Jika ingin contoh program searching yang lainnya, silahkan download pada link :
https://drive.google.com/file/d/1GYikXGDSaHZEJLr4ED2ZTbSweU20LHtI/view?usp=sharing
https://drive.google.com/file/d/1nk8u6DORb81BFy0ohTf4oU17MB_oJ1Zu/view?usp=sharing
https://drive.google.com/file/d/1RZx7slXN0wNBEXg-YuT0Y98CUR6qHREq/view?usp=sharing
https://drive.google.com/file/d/1m1MpQrSBRN3A5INrXEQGbVB7IAXDo22Q/view?usp=sharing
https://drive.google.com/file/d/1nk8u6DORb81BFy0ohTf4oU17MB_oJ1Zu/view?usp=sharing
https://drive.google.com/file/d/1RZx7slXN0wNBEXg-YuT0Y98CUR6qHREq/view?usp=sharing
https://drive.google.com/file/d/1m1MpQrSBRN3A5INrXEQGbVB7IAXDo22Q/view?usp=sharing
DAFTAR PUSTAKA
Muhidin,
Asep. 2010. Modul Kuliah Pemrograman
Bahasa C++, Bekasi; Penerbit Zeyrank Offset.
Arhami, Muhammad. 2010. “MODUL PRAKTIKUM
ALGORITMA DAN STRUKTUR DATA”. Pendidikan Teknik Informatika. Politeknik Universitas
Negeri Malang.
Rahmaddeni. 2012. “ANALISA PERBANDINGAN ALGORITMA PENCARIAN (SEARCHING
ALGORITM)”. Jurnal. Jurnal Sains dan Teknologi
Informasi, Vol. 1, No. 1.
0 komentar:
Posting Komentar