Pencarian Biner

Pencarian dalam array dengan waktu O(n) sudah baik, tetapi masih bisa dioptimalkan menjadi O(log n) menggunakan fungsi yang disebut Binary search. 

Kondisi untuk menggunakan Binary Search: Elemen array harus diurutkan secara menaik atau menurun.

Contohnya, 

int Arr[]={1,2,3,4,5};
int Brr[]={5,3,9,6,7};

Pada Arr, kita bisa menerapkan Binary search untuk menemukan elemen karena semua elemen Arr diurutkan secara menaik.

Kita tidak bisa menerapkan Binary Search pada Brr karena elemen Brr tersusun secara acak.

Logika Dasar

Periksa bagian tepat di tengah array, 

1. Jika nilainya sama dengan elemen yang dicari, tampilkan nilainya,
2.  jika nilainya lebih kecil dari elemen kunci, cari di sisi kanan sisa array, 
3.  jika nilainya lebih besar, cari di sisi kiri sisa array.

Ulangi proses ini sampai kamu menemukan elemen kunci yang dicari, jika tidak, kembalikan -1.

Proses Terperinci

1. Pertama, kita menginisialisasi 2 variabel untuk menandai awal dan akhir array. Lalu, gunakan while loop dengan kondisi bahwa nilai awal harus selalu lebih kecil dari nilai akhir.

    int s=0; //awal
    int e=n; //akhir
    
    while(s<=e){
    
    }

2. Cari bagian tengah elemen dengan menghitung (s+e)/2. Jika mid tepat sama dengan key, kembalikan nilainya.

    int s=0; //awal
    int e=n; //akhir
    
    while(s<=e){
    
        int mid=(s+e)/2;  //Titik tengah array

        if(arr[mid]==key){   //jika nilainya sama, kembalikan indeksnya
            return mid;
        }
    
    }

3. Jika bagian tengah lebih besar daripada elemen kunci, artinya elemen kunci harus berada di sisi kiri array. Karena itu, kita menggeser nilai akhir array ke mid-1. Sekarang, kita hanya memiliki array berukuran n/2, lalu kita mengulangi proses ini pada array tersebut.

    int s=0; //awal
    int e=n; //akhir
    
    while(s<=e){
    
        int mid=(s+e)/2;  //tengah array

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;         //geser batas akhir ke mid-1
        }
    
    }

4. Jika tidak satu pun pernyataan ini bernilai true, jelas bahwa elemen tersebut harus lebih besar daripada elemen tengah. Karena itu, kita mencari di bagian kanan array dan menggeser nilai awal array ke posisi mid+1.

    int s=0;
    int e=n;
    while(s<=e){
        int mid=(s+e)/2;

        if(arr[mid]==key){
            return mid;
        }
        else if(arr[mid]>key){
            e=mid-1;
        }
        else{
            s=mid+1;   //Pindahkan posisi awal ke mid+1
        }
    }

Jalankan program sampai kita menemukan elemennya. Jika elemen tidak ditemukan, kembalikan -1.

Kompleksitas Waktu

Pada setiap langkah, jumlah elemen menjadi setengahnya. Artinya, waktu eksekusi setiap langkah adalah setengah dari langkah sebelumnya. Ini berarti waktu berkurang secara logaritmik, sehingga kompleksitas waktu pencarian dengan Binary search adalah O(log n).