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:

`a[mid] == X`

, if the middle element is equal to X, we know that we have found a match.`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]`

.`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[200000];
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;
}
```