Binary Search Functions in C++ STL
About Binary Search Functions in STL
On this page we will discuss about binary search functions in STL which are used in C++. The Standard Template Library(STL) is a set of complete data structures and functions which can be used in C++. The binary search functions in C++ STL helps to find the occurrence if any element in an already sorted array..
In C++ programming language, there are mainly 3 types of operations which are performed using binary search :
1. Finding an element
2. Lower bound
3. Upper bound
1. Finding an element :
While finding an element using binary search, the function will return true if the element is present.Otherwise, it will return false.
Example
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector arr = { 10, 15, 20, 25, 30, 35 };
if (binary_search(arr.begin(), arr.end(), 15))
cout << "15 exists in vector";
else
cout << "15 does not exist";
cout << endl;
if (binary_search(arr.begin(), arr.end(), 23))
cout << "23 exists in vector";
else
cout << "23 does not exist";
cout << endl;
}
Output
15 exists in vector 23 does not exist
2. Lower Bound :
The lower bound function returns pointer to the position of num if the container contains only one occurrence of num. It returns a pointer to the first position of num if the container contains multiple occurrences of num. It returns pointer to the position of a number just higher than num, if the container does not contain an occurrence of num which is the position of the number when inserted in the already sorted array and sorted again. Subtracting the first position i.e vect.begin() from the pointer, returns the actual index.
Example
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector arr1 = { 10, 15, 20, 25, 30, 35 };
vector arr2 = { 10, 15, 20, 20, 25, 30, 35 };
vector arr3 = { 10, 15, 25, 30, 35 };
cout << "The position of 20 using lower_bound "
" (in single occurrence case) : ";
cout << lower_bound(arr1.begin(), arr1.end(), 20)
- arr1.begin();
cout << endl;
cout << "The position of 20 using lower_bound "
"(in multiple occurrence case) : ";
cout << lower_bound(arr2.begin(), arr2.end(), 20)
- arr2.begin();
cout << endl;
cout << "The position of 20 using lower_bound "
"(in no occurrence case) : ";
cout << lower_bound(arr3.begin(), arr3.end(), 20)
- arr3.begin();
cout << endl;
}
Output
The position of 20 using lower_bound (in single occurrence case) : 2 The position of 20 using lower_bound (in multiple occurrence case) : 2 The position of 20 using lower_bound (in no occurrence case) : 2
3. Upper Bound:
The upper bound function returns pointer to the position of next higher number than num if the container contains one occurrence of num. It returns pointer to the first position of the next higher number than the last occurrence of num if the container contains multiple occurrences of num. It returns pointer to position of next higher number than num if the container does not contain an occurrence of num. Subtracting the first position i.e vect.begin() from the pointer, returns the actual index.
Example
#include<bits/stdc++.h>
using namespace std;
int main()
{
vector arr1 = { 10, 15, 20, 25, 30, 35 };
vector arr2 = { 10, 15, 20, 20, 25, 30, 35 };
vector arr3 = { 10, 15, 25, 30, 35 };
cout << "The position of 20 using upper_bound"
" (in single occurrence case) : ";
cout << upper_bound(arr1.begin(), arr1.end(), 20)
- arr1.begin();
cout << endl;
cout << "The position of 20 using upper_bound "
"(in multiple occurrence case) : ";
cout << upper_bound(arr2.begin(), arr2.end(), 20)
- arr2.begin();
cout << endl;
cout << "The position of 20 using upper_bound"
" (in no occurrence case) : ";
cout << upper_bound(arr3.begin(), arr3.end(), 20)
- arr3.begin();
cout << endl;
}
Output
The position of 20 using upper_bound (in single occurrence case) : 3 The position of 20 using upper_bound (in multiple occurrence case) : 4 The position of 20 using upper_bound (in no occurrence case) : 2
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment