Searching in STL C++
About Searching in STL
Searching is defined as finding the element in group of elements arranged in the particular order. Binary search provides an effective way to find elements in sorted collections such as arrays, vectors, and lists. Searching in STL is done by inbuilt function binary_search().
How Binary Search Work:
Implementing Binary Search in C++ using STL.
Syntax of binary_search() :
binary_search(start_address, end_address, element to be find);
This algorithm’s primary principle is to divide an array in half repeatedly (divide and conquer) until either the element is located or all the elements have been used up. It operates by comparing the middle item in the array with our target; if they match, it returns true; if they don’t, the left sub-array is searched. The search is carried out in the appropriate sub-array if the middle term is less than the target element.
Array must be sorted to apply binary search in stl
Example of Searching in STL :
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {2,4,3,43,4,35,67,99,85,34};
int n = sizeof(arr)/sizeof(arr[0]);
int a = 43;
sort(arr, arr+n);
if(binary_search(arr, arr+n, a)){
cout<<"Element " << a<<" is present in the array";
}
else{
cout<<"Element " << a <<" is not found in the array";
}
return 0;
}
Output :
Element 43 is present in the array
In the above program, we take the array and used sort function to sort the elements , by using binary_search we check elements a is present in the array or not.
Example of Searching in STL:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {2,4,3,43,4,35,67,99,85,34};
int n = sizeof(arr)/sizeof(arr[0]);
int a = 100;
sort(arr, arr+n);
if(binary_search(arr, arr+n, a)){
cout<<"Element " << a<<" is present in the array";
}
else{
cout<<"Element " << a <<" is not found in the array";
}
return 0;
}
Output :
Element 100 is not found in the array
In the above program, we take the array and used sort function to sort the elements , by using binary_search we check elements a is present in the array or not.
lower_bound() and upper_bound() Functions
STL provides two essential functions for performing binary search on sorted containers: lower_bound() and upper_bound().
The lower_bound() Function
The lower_bound() function returns an iterator pointing to the first element in the container that is not less than the target value. It effectively identifies the range’s lower bound where the target element could be present.
Lower Bound Example :
#include<bits/stdc+.h>
using namespace std;
int main() {
std::vector nums = {1, 2, 2, 3, 4, 5, 5, 5, 6, 7};
// Binary search requires the input range to be sorted.
std::sort(nums.begin(), nums.end());
int target = 5;
// Using lower_bound to find the first occurrence of the target.
std::vector::iterator lower = std::lower_bound(nums.begin(), nums.end(), target);
if (lower != nums.end() && *lower == target) {
std::cout << "Lower bound of " << target << " is at index: " << std::distance(nums.begin(), lower) << std::endl;
} else {
std::cout << target << " not found in the vector." << std::endl;
}
return 0;
}
On the other hand, the upper_bound() function returns an iterator pointing to the first element in the container that is greater than the target value. It helps identify the upper bound of the range.
Upper Bound Example:
#include <bits/stdc++.h>
using namespace std;
int main() {
std::vector nums = {1, 2, 2, 3, 4, 5, 5, 5, 6, 7};
// Binary search requires the input range to be sorted.
std::sort(nums.begin(), nums.end());
int target = 5;
// Using upper_bound to find the first element greater than the target.
std::vector::iterator upper = std::upper_bound(nums.begin(), nums.end(), target);
if (upper != nums.end()) {
std::cout << "Upper bound of " << target << " is at index: " << std::distance(nums.begin(), upper) << std::endl;
} else {
std::cout << "There is no element greater than " << target << " in the vector." << std::endl;
}
return 0;
}
Use Cases of Binary Search in STL C++
- Searching Elements in Sorted Containers
The primary use case of binary search is locating specific elements in sorted containers. This proves particularly valuable when dealing with extensive datasets where linear search would be highly inefficient.
- Finding Frequency of Elements
Binary search can also be used to find the frequency of a particular element in a sorted container. By utilizing lower_bound() and upper_bound(), we can determine the count of occurrences efficiently.
Conclusion
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