Day 14 | Binary Search | C++

Have you ever used a dictionary? If you are looking for some word, you open a random page and then decide to look ahead or behind right? Binary Search is the same algorithm that it is also called dictionary search by many.

Let's learn what binary search is officially

Binary Search is a searching algorithm in a sorted list.

Remember the keyword sorted here.

Simple Concept

You have an array of size equal to N. You want to find if an element K is present in the array or not.

Since the array is sorted, we see the middle element. If the middle element is greater than the element, then we know the element won't exist in the right half, thus reducing search space to N/2

We keep doing this till either we find an element or the search space is no longer valid.

bool binary_search(vector<int> arr, int element){
    int start = 0; // start - start of search space
    int end = arr.size() - 1; // end - end of search space
    while (start <= end) { // valid search space starts before it ends
        int mid = (start + end) / 2;
        if(arr[mid] == element)return true;
        if(arr[mid] > element)end = mid - 1;
        else start = mid + 1;
    }
    return false; // We did not find the element
}

So in simple works binary search just keep breaking our array into half -

You can use this to visualize how binary search works

Here we are returning true/false, we can also return the index of the position of the element and -1 in case it is not there.

STL binary_search

STL provides a binary_search method with which you can do the same as above in the contest.

The Following gives the same result as the code written above

binary_search(arr.begin(), arr.end(), element);

STL upper_bound / lower_bound

Upper_bound are very useful methods to find the first element which is strictly greater than the element we are searching for.

Lower_bound is the same as upper bound but instead of strictly larger, it finds larger or equal.

Ignore this line if confused - Upper bound returns the iterator of the type of container it is searching on.

You can find indexes in vectors or arrays like this

int index = upper_bound(arr.begin(), arr.end(), element) - arr.begin();

Similarly for upper_bound

int index = lower_bound(arr.begin(), arr.end(), element) - arr.begin();

Binary Search on the answer

This is the most common use of binary search in competitive programming.

For this remember that we run a binary search on a sorted list, now if we think of a whole number, then it is sorted as well. Even real numbers are sorted.

Let's understand with an example -

Problem - Implement Sqrt(X)

Sample input 0 - 121

Sample output 0 - 11

Sample input 1 - 27

Sample output 1 - 5

Constraints - 1 <= X <= 10^8

We know that since X is at max 10^8, therefore answer can be at most 10^4. We need to know the lowest possible answer and also the high possible answer as those will be our search spaces.

Now let's say we find the middle value of our search space mid, then if mid^2 is greater than X then we know that mid+1, mid+2,...infinity cannot have our answer as well.

And in case it is smaller, then mid can be the answer and we don't need to verify for lower values as well. Why mid can be the answer is because it not necessary that we will get perfect answers. As in TC2, the answer for 27 is 25. Binary Search actually breaks your search space into two parts - an impossible section and a possible section.

Implementation -

int sqrt(int x){
    int lo = 1, hi = 10000, ans;
    while(lo <= hi){
        int mid = (start + end) / 2;
        if( mid * mid > x) { // Then x ... infinity is impossible section
            hi = mid - 1;
        }
        else { // then start .. mid is possible section
            ans = mid; // storing maximum possible section value
            lo = mid + 1;
        }
    }
    return ans;
}

Some Questions for you to try which we will discuss in upcoming blogs -

1. Vanya and Lanterns

2. Hamburgers

3. Books

4. K-th Not Divisible by n