Binary Search dan interpolation search

pengertian Binary Search.

                 

                      Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya.

            Dalam Pencarian Binary Search, Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian. Prinsip pencarian biner adalah:

         Data diambil dari posisi 1 sampai posisi akhir N Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar? Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1 Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1 Jika data sama, berarti ketemu

contoh program binary search
//binary searching,
//program bisa jalan jika data sudah terurut
#include <iostream.h>
#include <conio.h>

int data[10]={1,3,4,7,12,25,40,65,78,90};
int binary_search(int cari)


{
int l,r,m;
int n=10;
l=0;
r=n-1;
int ketemu=0;
while (l<=r && ketemu==0)
{
m=(l+r)/2;
if (data[m]==cari)
ketemu=1;
else
if(cari<data[m])
r=m-1;
else l=m+1;
}
if(ketemu==1) return 1; else return 0;
}

void main()
{
clrscr();
int cari, hasil;
cout<<"masukan data yang ingin di cari= ";
cin>>cari;
hasil = binary_search(cari);
if(hasil==1)
{
cout<<"data ada!"<<endl;
}
else
if(hasil==0)
  cout<<"data tidak ada!"<<endl;
  getch();
}

contoh ke dua


#include <iostream.h>
#include <conio.h>

int cari_biner(int array[],int ukuran, int elemen);

void main()
{
const int ukuran=10;
int array[ukuran]={0,6,9,12,20,23,29,32,47,79};
cout<<"isi dari array : "<<endl;
for(int i=0;i<ukuran;i++)
cout<<" "<<array[i];

int elemen;
int tanda;
cout<<"\n masukkan data yang dicari : ";
cin>>elemen;

tanda= cari_biner(array,ukuran,elemen);
if (tanda!=-1)
cout<<"\n data tersebut ditemukan pada posisi : array["<<
tanda<<"],"<<" atau deret ke-"<<(tanda+1);

else
cout<<"\n data tersebut tidak ditemukan ";
getch();

}

int cari_biner(int array[],int ukuran,int elemen)
{
int start=0;
int end=ukuran - 1;
int middle;
int posisi=-1;
middle=(start + end ) / 2;
do
{
if(elemen<array[middle])
end=middle-1;
else if (elemen>array[middle])
start=middle+1;
middle=(start+end)/2;

}
while(start<=end && array[middle]!=elemen);

if(array[middle]==elemen)
posisi=middle;
return posisi;

}

sumber http://allaboutalgoritma.blogspot.com/2009/06/binary-search.html 



 INTERPOLATION SEARCH

Interpolation Search

Interpolation search merupakan salah satu metode pencarian yang dapat digunakan. Seperti pada binary search, data yang harus diurutkan terlebih dahulu, sebelum dapat dilakukan pencarian dengan metode ini. Pada metode pencarian ini, kita mencoba menebak letak data yang kita cari, dengan perhitungan

·         Jika data [posisi] > data yg dicari, high = pos – 1

·         Jika data [posisi] < data yg dicari, low = pos + 1

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 
 import java.util.Scanner;

     public class Interpolation {
     public static int interpolationSearch(int[] sortedArray, int toFind)
    {
        int low = 0;
        int high = sortedArray.length - 1;
        int mid;
       
        while (sortedArray[low] <= toFind && sortedArray[high] >= toFind)
        {
            if (sortedArray[high] - sortedArray[low] == 0)

                return (low + high)/2;
             mid = low + ((toFind - sortedArray[low]) * (high - low)) / (sortedArray[high] - sortedArray[low]); 
             if (sortedArray[mid] < toFind)
                 low = mid + 1;
            
             else if (sortedArray[mid] > toFind)
                 high = mid - 1;
             else
                 return mid;
        }
        if (sortedArray[low] == toFind)
            return low;     
        else
            return -1;
    }   
       
       
    public static void main(String[] args)
    {
        Scanner scan = new Scanner( System.in );       
       
        int n, i;
        System.out.println("masukkan jumlah elemnt bilangan bulat");
        n = scan.nextInt();
        int arr[] = new int[ n ];
        System.out.println("\nEnter "+ n +" masukkan data bilangan bulat");
       
        for (i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        System.out.println("\nEnter element untuk mencari : ");
        int key = scan.nextInt();
        int result = interpolationSearch(arr, key);
        if (result == -1)
            System.out.println("\n"+ key +" data tidak ditemukan");
        else
            System.out.println("\n"+ key +" data berada pada posisi "+ result);
    }   
}