Binary search algorithms are everywhere, and for good reason. They embody a simple yet powerful idea. In general, algorithms are named with purpose. Let’s take a closer look at this algorithm through an example problem.

## Problem#

We are given an ascending sequence of length `N` and `Q` requests. Each request consists of a number, and the answer indicates whether that number exists in the sequence. `1 <= N, Q <= 10^5, abs(a[i]) <= 10^9`.

## Analysis#

For each request, check whether the number is equal to any number in the sequence. In the worst case, we will perform `N` operations for each request. This means that in total, we will perform `Q*N` or `10^10` operations. We can’t wait for it to finish working, right!

So, how can we solve this quickly? Note that the sequence is in ascending order. Suppose we want to determine whether the number X is present in a given sequence. First, we perform a single operation to access the value of the middle element of the sequence. If the index of the middle element is `mid`, it can be calculated as `mid = (n + 1) / 2`.

Here are some things to watch out for:

1. `a[mid] == X`, if the middle element is equal to X, we know that we have found a match.
2. `a[mid] > X`, or If the middle element is greater than X, then every element with an index from `[mid, mid+1,..., n]` is clearly greater than the number we are looking for. Then, there is no need to check the number X with all of these. If the number X is in this sequence, its index clearly in the interval `[1, 2, ..., mid]`.
3. `a[mid] < X`, then, all elements with indices `[1, 2, ..., mid]` are clearly less than the number we are looking for. Then, we don’t need to check the number X with all of these. If the number X is in this sequence, its index is clearly in the interval `[mid+1, mid+2, ..., n]`.

If conditions 2 and 3 hold, we still cannot determine whether X is in the sequence. However, if we apply the same idea again, we can search in a smaller interval. In case 2, we search in the interval `[1, mid-1]`, and in case 3, we search in the interval `[mid+1, N]`. By dividing the sequence into two parts, we can perform a worst-case of `log(N)` operations, resulting in a total of `Q*log(N)` operations.

``````#include <bits/stdc++.h>
using namespace std;

int n, q, a;

bool BS( int X ) {
int L = 1, R = n;

while( L <= R ) {
int mid = (L+R)/2;

if( a[mid] == X ) {
return true;
}

if( a[mid] > X ) {
R = mid-1;
} else {
L = mid+1;
}
}
return false;
}

int main() {
cin >> n >> q;

for(int i = 1; i <= n; i++) {
cin >> a[i];
}

while( q-- ) {
int x; cin >> x;

if( BS( x ) ) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
``````