binary_search
binary_search(start_ptr, end_ptr, num): This function returns true if the element is present in the container, else returns false. The start_ptr variable holds the starting point of the binary search and end_ptr holds the ending position of binary search space and num is the value to be found.
Coding implementation of binary_search function:
CPP
// C++ code to demonstrate the working of binary_search()#include <bits/stdc++.h>using namespace std;// Driver's codeint main(){ // initializing vector of integers vector<int> arr = { 10, 15, 20, 25, 30, 35 }; // using binary_search to check if 15 exists if (binary_search(arr.begin(), arr.end(), 15)) cout << "15 exists in vector"; else cout << "15 does not exist"; cout << endl; // using binary_search to check if 23 exists if (binary_search(arr.begin(), arr.end(), 23)) cout << "23 exists in vector"; else cout << "23 does not exist"; cout << endl;} |
15 exists in vector 23 does not exist
Time Complexity: O(log N) – where N is the number of elements in the array.
Auxiliary Space: O(1)
Binary Search functions in C++ STL (binary_search, lower_bound and upper_bound)
Binary search is an important component in competitive programming or any algorithmic competition, having knowledge of shorthand functions reduces the time to code them. Binary search is the most efficient search algorithm.
Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log N).
General operations performed using binary search:
- finding an element
- lower_bound
- upper_bound