Binary Search

Binary Search

Introduction:

Binary search is one of the most important algorithms for competitive programming. You may find other uses of binary search too, these are just a few topics mentioned that use binary search heavily:

1. Array problems

2. Geometry problems

Let me give you a real-life example, imagine you walked into a room with some numbered chairs (say 1 to 1000). Now you come to know that you have to sit on the chair numbered 563, of course, you could find it by walking in a straight path and looking at each of the chair numbers. But for the sake of understanding binary search assume that you can jump to any chair within a fraction of time,

  • First, jump to the chair number numbered 500 ((1+1000)/2). Now you see that the number 563 is greater than 500. So there is no need to search 563 at the left portion.
  • You then search between 500 and 1000 and land up at 750. The search interval now reduces to 500 and 750.

You follow the same process of eliminating regions until you reach a chair numbered 563. You can see that the elimination of search regions results in a very fast algorithm.

You follow the same process of eliminating regions until you reach chair numbered 563. You can see that the elimination of search regions results in a very fast algorithm.

This algorithm is used when the search space is monotonic in nature. What I mean to say is that you may not find chair 5 using the same algorithm if the chairs were placed in random order.

Now let’s look at other applications of binary search. It can be used to find a value that satisfies an equation that is monotonic in nature. For example, take an equation, 𝑥2−3 > 0 and 𝑥 > 0 should be always true. Also, you need to find the minimum value that would satisfy the equation.

The values of x that satisfy the equation should be more than or equal to 2, i.e., the function is monotonic in nature.

The answer can be found using binary search. The code-snippet using C++ is given below,

void solve() {
    int low = 0 ,high = 10000, mid; 
    while(low <= high) 
    { 
        mid = (low + high) / 2; 
        if(mid * mid - 3 > 0) { 
            high = mid - 1; 
        } else { 
            low = mid + 1; 
        } 
    } 
    cout << low << endl; 
} 
 
Output : 2 

You can practice some of these questions which will give you a better insight,

Sagheer and Nubian Markets
Anton and Fairy Tale

No Comments

Post A Comment