Things that we will learn in this article.
- What is Binary Search Algorithm and Why do we use it?
- Binary Search Algorithm for Checking whether the number is present in the given array or not.
- Code Implementation for the above Problem.
- Practice Problems
- Conclusion
What is Binary Search Algorithm and Why do we use it?
As the name suggests "Binary Search" is a search algorithm that can be used to solve a wide variety of problems.
To motivate you let me take an example of the sorted array which consists of N element and we need to answer Q queries and in each query, we need to answer whether the given number X is present or not?
- So if we solve this problem using linear search it will have a time complexity of O( NQ ) which is huge and it will lead to TLE ( Time Limit Exceed Error in Competitive Programming Contest ). And here if we use binary search then we can answer this in just O( QlogN ) time complexity which is awesome right?
- To be more precise for each query it will take almost then logN iteration.
So now let's discuss the Binary Search Algorithm using the above problem of Checking whether the given number is present in the array or not?
So to understand this let us take a sorted array A with 10 elements, for example
\[A = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} \]
Now let us say that we want to check whether the number X = 4 is present in the array or not. So how can we do this?
The concept here is to always compare the given number with the middle element of the array and take the decision on whether the number is matched, or we have a look into the left part of the array or right part.
- So let us take three-variable L=0 ( Starting index of Array ) and R=9 ( Ending index of Array ).
- And M ( middle index )
\[ M = \frac{ L + R }{2} \]
- Now Compare this according to the following condition
if (A[M] == X) {
cout << "Number Found !" << endl;
break;
} else if (A[M] < X) {
L = M+1;
} else {
R = M-1;
}
- if A[M] == X then we have found the Number so simply break the loop.
- if A[M] < X means that the number lies in the right of the Middle Element and this we can guarantee because the array is sorted. Hence sorted array is required to use Binary Search.
- if A[M] > X means that the number lies in the left of the Middle Element as the array is Sorted.
Simulation of Above Example:
X = 4 and A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
- L = 0, R = 9 so M = 4
- A[4] > X so we need to search for X in Left Side so R = 3 ( M-1 ), i.e. first 5 element ( Red Coloured )
A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
- Now L = 0, R = 3 so M = 1
- A[1] < X so we need to search for X on Right Side so L = 2 ( M+1 ), i.e we need to search in the index range [ L, R ].
A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
- Now L = 2, R = 3 so M = 2
- A[2] < X so we need to search for X on Right Side so L = 3 ( M+1 ), i.e we need to search in the index range [ L, R ].
- Now L = 3, R = 3 so M = 3
- A[3] == X, so we have found the given number hence break the loop.
- We just took 3 iterations to check whether the number is present in the array or not. This is the Magic of Binary Search.
A = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
C++ Implementation to Check whether the number X is present in the array or not using Binary Search.
- We will be printing "YES" if the Number X exists else "NO".
- Iterative Code Implementation.
#include <iostream>
#include <vector>
using namespace std;
#define NL "\n"
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int x;
cin >> x;
int l = 0, r = n - 1;
bool ok = false;
while (r >= l) {
int m = (l + r) / 2;
if (a[m] == x) {
ok = true;
break;
} else if (a[m] < x) {
l = m + 1;
} else {
r = m - 1;
}
}
if (ok)
cout << "YES" << NL;
else
cout << "NO" << NL;
}
int32_t main() {
std::ios_base::sync_with_stdio(false);
solve();
return 0;
}
Practice Problems
- Just try to Implement this Code on your own using Recursion.
In the upcoming article, we will look into a variety of problems which we can solve using Binary Search and then problems from Codeforces, CodeChef will be shared here for your practice.
Conclusion
In this article you have learned about Binary Search, Why do we use this? How do we use this in simple problem solving like checking whether the given number is present in the array or not? Why do we need to use a sorted array and at last we have looked into the iterative approach of Binary Search Implementation code.
The related articles which you should read after this article.
- Finding the largest number smaller the given number using binary search.
- Finding the smallest number larger than then given number using binary search.
- Solving Problem for Binary Search by Answer
- Using Binary Search with Floating-Point Numbers in Minimization and Maximization Problem
- Minimization and Maximization Problem Solution using Binary Search
- Finding the Maximum Average of a SubSet of Length at least D
- Finding K-th Number in Ascending element of some Set
If there is any error or you have any doubt in the article then do ask us through the comment, we will be happy to help you.
If you think that this article has helped you to learn something then do share this with your friends.
Thank You for Reading.
Tags:
Binary Search