searching

searching

Ada beberapa metode mencari data di dalam sekumpulan data yang bertipe sama,
yaitu:
- Metode Pencarian Beruntun (Sequential Search)
- Metode Pencarian Bagi dua (Binary Search)

Pencarian (Searching) merupakan proses yang fundamental dalam pemrograman.
menemukan data (nilai) tertentu di dalam sekumpulan data yang bertipe sama
Fungsi pencarian itu sendiri adalah untuk memvalidasi (mencocokkan) data.

contoh progeram:

#include
#include
int main(int argc, char* argv[])
{
int X,i,k;
int L[10] = {20,15,22,14,12,10,24,19,18,16};
printf("Data yang akan dicari = ");scanf("%d",&X);
k = 0;
for(i=0;i<=9;i++)
{
if(L[i]==X)
{
printf("Data ditemukan di elemen %d \n",i);
k++;
} }
if(k==0)
{
printf("Data tidak ditemukan \n");
}
printf("Jumlah data yang ditemukan = %d",k);
getch();
return 0;
}


Binary Search :

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 Binary Search:

Konsep dasar metode ini adalah membagi 2 jumlah elemennya,
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.


Langkah-langkah Binary Search:

1. Asumsikan data terurut secara horizontal dari indeks 0 sampai n-1, untuk menggunakan istilah kanan dan kiri.
2. Misalkan kumpulan data yang berjumlah n adalah larik L, dan data yang akan dicari adalah X.
3. Tentukan nilai indeks awal i = 0 dan indeks akhir j = n-1.
4. Tentukan apakah data terurut menurun atau menaik dengan menggunakan membandingkan apakah elemen paling kiri L[0] lebih dari atau kurang dari elemen paling kanan L[n-1].
Jika data di elemen paling kiri L[0] > data di elemen paling kanan L[n-1], maka data terurut menurun.
Jika data di elemen paling kiri L[0] < data di elemen paling kanan L[n-1], maka data terurut menaik.
5. Asumsikan bahwa data terurut menaik (tergantung hasil dari nomor 3).
6. Misalkan variabel k adalah indeks paling tengah, diperoleh dengan rumus:
k = (i + j) div 2.
7. Periksa, jika L[k] = X, maka data dicari langsung ketemu di elemen k.
8. Jika nomor 7 tidak terpenuhi, periksa jika L[k] < X, maka pencarian berikutnya dilakukan di sisi kanan indeks k, lakukan proses seperti pada nomor 6, dimana nilai indeks i sekarang sama dengan nilai indeks k sebelumnya.
i = k.
k = (i + j) div 2.
Dan seterusnya sampai nilai X dicari ketemu atau tidak sama sekali.
9. Jika nomor 8 tidak terpenuhi, maka tidak pasti nilai L[k] > X, maka pencarian berikutnya dilakukan di sisi kiri indeks k, lakukan proses seperti pada nomor 6, dimana nilai indeks j sekarang sama dengan nilai indeks k sebelumnya.
j = k.
k = (i + j) div 2.
Dan seterusnya sampai nilai X dicari ketemu atau tidak sama sekali.
10. Jika data terurut menurun, maka tukar kondisi yang ada di nomor 8 dan 9.

Posted in: