Searching in STL C++

July 22, 2023

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().
Searching in stl

How Binary Search Work:

Binary search operates by repeatedly dividing the search space in half, comparing the middle element with the target value, and narrowing down the search to the appropriate subarray. This process continues until the target element is found or the search space is exhausted. Time Complexity : O(log n)

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 :

Run 
#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.

Loop Types in C++

Decision Making in C++

Array in C++

String in C++

Function in C++

Example of Searching in STL:

Run 
#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 :
Run 
#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;
}
The upper_bound() Function :

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:
Run 
#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
Binary search in STL C++ offers a powerful and efficient way to search for elements in sorted containers. Its logarithmic time complexity makes it an essential algorithm for various applications, especially those dealing with extensive datasets. By understanding its strengths and limitations, developers can leverage binary search effectively to enhance application performance.

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

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

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout