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

As you can see, when gets larger, the value of will be significantly smaller than , 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;
}

One thought on “MCO Training Camp Day 1: #2 Binary Search”

[…] the eggs were unlimited, my best strategy would be using Binary Search. That is, we search from the 50th floor. If the egg breaks, we drop it again on the 75th floor. If […]

[…] the eggs were unlimited, my best strategy would be using Binary Search. That is, we search from the 50th floor. If the egg breaks, we drop it again on the 75th floor. If […]

LikeLike