# MCO Training Camp Day 1: #2 Binary Search

Binary Search was the second lesson at the camp. The power of Binary Search is that its time complexity is only $O(\log_2 n)$, way more efficient than linear search $O(n)$. The graph below shows the growth of $\log_2 n$ (red) and $n$ (blue).

Image Credit: MSE

As you can see, when $n$ gets larger, the value of $\log_2 n$ will be significantly smaller than $n$, which means the time required for Binary Search is much less than Linear Search.

Here is a short video explaining the Binary Search Algorithm:

Below is the code for Binary Search Algorithm:

C++ Implemetation

```bool Binary_Search(int A[], int length, int target){
// Search for target in array A.
int lo = 0;
int hi = length - 1;
bool exist;
while (lo <= hi){
int mid = (lo + hi) / 2;
if (A[mid] == target){
exist = true;
break;
}
else if(A[mid] > target){
hi = mid - 1;
exist = false;
}
else{
lo = mid + 1;
exist = false;
}
}
return exist;
}
```