#### Author: Sayed Aulia
<div style="text-align: justify">

Katakanlah kita memiliki suatu array $a$ berisikan $N$ buah bilangan bulat, katakanlah elemen pada array tersebut telah diurutkan dari urutan terkecil hingga terbesar dan anggaplah array tersebut berisikan $a = \{1, 3, 6, 7, 9, 14, 21\}$. Dengan keterangan tersebut kitapun diberikan sebuah pertanyaan, "Pada indeks berapakah element dengan nilai 9 berada atau tentukan apakah elemen dengan nilai 9 sama sekali terdapat di dalam array $a$ atau tidak".

Tentunya solusi yang nampak jelas adalah kita dapat melakukan pencarian pada seluruh elemen pada array secara linear (artinya kita dapat mengiterasi setiap elemen satu persatu dari elemen $a_1$ hingga $a_N$ hingga kita temukan elemen $a_i$ yang kita inginkan sebelum program melakukan `break`), menggunakan solusi ini, pencarian dapat dilakukan dengan kompleksitas $\mathcal{O}(N)$. Tetapi pencarian dapat dioptimisasi sehingga kompleksitasnya menjadi $\mathcal{O}(\log N)$ saja menggunakan *binary search*.

> Perlu diingat bahwa binary search hanya dapat digunakan apabila nilai pada array sudah diurutkan.

Sebenarnya sangat mungkin Anda pernah melakukan *binary search* di dunia nyata, contoh yang paling jelas adalah saat kita menggunakan buku kamus. Jika kita ingin mencari kalimat *Pemrograman* pada kamus, tentunya kita tidak akan membuka kamus dari halaman pertama dan mencarinya secara linear halaman-perhalaman, yang tentunya kita akan lakukan adalah kita membuka kamus dari tengah buku dan kita dapati bahwa kita berada pada halaman yang memuat kata dengan awalan `M`. Karena `M` muncul lebih awal daripada `P` kita tahu kita tidak perlu mencarinya pada halaman sebelum `M` muncul. kita telah mempersempit ruang pencarian kita yang tadinya memiliki jangkauan `A`-`Z` menjadi `M`-`Z` saja. kita pun melakukan pembelahan pada tengah-tengah jangkauan pencarian yang baru, katakanlah kita mendapatkan halaman dengan awalan huruf `T`, karena `T` muncul setelah `P` maka kita ingin mengabaikan halaman yang berada di kanan halaman yang memuat huruf `T`, jangkauan pencarian baru kita hanyalah dari `M` hingga `T`. Kitapun ingin melakukan prosedur ini hingga mendapatkan kalimat *pemrograman* yang kita inginkan. Katakanlah kamus memiliki 1024 halaman, dengan operasi *binary search* ini kita hanya perlu melakukan kira-kira $\log_2 (1024) = 10$ operasi saja.

#### Contoh Soal
Diberikan sebuah array $a$ dengan besar $N$, tentukan apakah bilangan bulat $k$ berada pada array $a$. Jika $k$ ada pada $a$, keluarkan indeksnya, jika tidak keluarkan `-1`.

#### Solusi

Kita dapat mengimplementasikan strategi binary search pada soal tersebut. Saat menggunakan binary search pertama-tama kita ingin menginisialisasikan jangkauan pencarian dari indeks $l$ hingga $r$, awalnya nilai $l = 1$ dan $r = N$. Untuk setiap operasi *tengah*nya kita ingin mendefisikan indeks tengah pada pencarian sebagai $m = \lfloor{(l + r)/2\rfloor}$ (fungsi floor mencegah nilai $m$ berbentuk desimal). Jika nilai elemen pada indeks $m$ ternyata lebih besar dari elemen $a_i$ yang dicari maka kita ingin mengabaikan rentang pencarian yang lebih besar dari $m$ dengan membuat nilai $r = m - 1$, jika sebalikanya nilai elemen pada indeks $m$ lebih kecil daripada nilai yang dicari maka kita ingin mengabaikan rentang pencarian yang lebih kecil dari $m$ dengan membuat nilai $l = m + 1$. Kita lakukan operasi ini berkali-kali hingga kita dapatkan nilai $a_i$ yang kita inginkan atau hingga nilai $l > r$ yang artinya nilai $a_i$ tidak ditemukan pada array.

Kita dapat menuliskan programnya sebagai berikut:

int N, k;
int a[100005];

int binarySearch(int k){
    int l = 1, r = N;
    while(l <= r){
        int m = (l + r)/2;
        if(a[m] < k) l = m + 1;
        else if(a[m] > k) r = m - 1;
        else if(a[m] == k) return m; // m merupakan indeks elemen yang bernilai k.     
    }
    return -1; // nilai k tidak ditemukan pada array.
}

int main(){

    cin >> N >> k;
    
    for(int i = 1; i <= N; i++){
        cin >> a[i];
    } sort(a, a + (N + 1)) // Binary Search hanya berfungsi pada array yang sudah diurutkan.
    
    cout << binarySearch(k) << endl;
}

Solusi ini memberikan kompleksitas $\mathcal{O}(\log N)$.

## Binary Search the Answer

Terkadang kita dapat melakukan *tebakan* pada jawaban menggunakan binary search, kita sebut strategi ini sebagai *binary search the answer*. Pertimbangkan soal berikut: