Pencarian Aray Menggunakan Metode Binary search Interpolation search

Metode pencarian yang kedua adalah
binary search , pada metode pencarian ini, data harus diurutkan terlebih dahulu. Pada metode pencarian ini, data dibagi menjadi dua bagian (secara logika), untuk setiap tahap pencarian. Algoritma binary search :
1. Data diambil dari posisi 1 sampai posisi akhir N
2. Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2
3. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
4. Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
5. Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
6. Jika data sama, pencarian dihentikan, data ditemukan.
7. Jika sudah melewati semua posisi, data tidak ditemukan, pencarian dihentikan. Contoh 3 source binary search


#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
   int data[100], batas, flag=0, i, cari, awal, tengah, akhir;
   awal=0;
   cout<<"Masukkan banyaknya data yang di inginkan : "; cin>>batas;
   for (i=0; i<batas; i++){
    cout<<"Masukkan data "<<i+1<<" : "; cin>>data[i];
   }
   cout<<endl;
   cout<<"data "<<endl;
   for (i=0; i<batas; i++){
    cout<<data[i]<<" ";
   }
   akhir=batas;
    cout<<endl;
   cout<<"data yang dicari "; cin>>cari;
    while (awal<=akhir && flag==0){
        tengah=(awal+akhir)/2;
        cout<<"data tengah --> "<<tengah<<" data ke-"<<data[tengah]<<endl;
        if (data[tengah]==cari){
            flag=1;
            break;
        }
        else if (data[tengah]<cari){
            awal=tengah;
            cout<<"cari di bagian kanan"<<endl<<endl;
        }
        else {
            akhir=tengah-1;
            cout<<"cari di bagian kiri"<<endl<<endl;
        }
    }
    cout<<endl;
     if (flag==1) {
        cout<<"DATA DITEMUKAN !"<<endl;
        for (i=0; i<10; i++){
            if (data[i]==cari)
            cout<<"Data berada pada index ke-"<<i+1<<endl;
        }

     }
    else
        cout<<"NOT FOUND !";
}

I n t e r p o l a t i o n s e a r c h
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 Contoh 4
source code interpolation sear ch :