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[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;
}