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).

binary

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;
}
Advertisements
MCO Training Camp Day 1: #2 Binary Search

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s