# std::binary_search() in C++

In this article, we are going to see **C++ STL function binary_search()** which uses the standard binary search algorithm to search an element within a range.

Submitted by Radib Kar, on July 15, 2020

## binary_search() as a STL function

**Syntax:**

bool binary_search ( ForwardIterator first, ForwardIterator last, const T& value);

Where,

- ForwardIterator first = iterator to start of the range
- ForwardIterator last =iterator to end of the range
- T &value = reference to searching element which is of datatype
*T*,*T*can be any inbuilt datatype or user-defined data type

**Return type:** bool

*True*- if element found in the range*False*- If the element not found in the range

The above syntax is used to compare elements using standard comparison operators. Two elements *a* & *b* are said to be equal *if (!(a<b) && !(a>b))*.

We can also define the user-defined comparator for comparing. The syntax with user-defined comparator is like below:

bool binary_search( ForwardIterator first, ForwardIterator last, const T& val, Comparator comp);

Using the above syntax two elemnts a & b would be equal *if (!comp(a<b) && !comp(a>b))*.

## 1) Using default comparator

#include <bits/stdc++.h> using namespace std; int main() { vector<int> arr{ 3, 2, 1, 4, 5, 6, 7 }; //tp perform binary search we need sorted //input array sort(arr.begin(), arr.end()); int search_element = 4; //ForwardIterator first=arr.begin() //ForwardIterator last=arr.end() //const T& val=search_element if (binary_search(arr.begin(), arr.end(), search_element)) { cout << "search_element " << search_element << " found\n"; } else cout << "search_element" << search_element << " not found\n"; search_element = 7; //ForwardIterator first=arr.begin() //ForwardIterator last=arr.begin()+arr.size()-1 //const T& val=search_element if (binary_search(arr.begin(), arr.begin() + arr.size() - 1, search_element)) { cout << "search_element " << search_element << " found\n"; } else cout << "search_element " << search_element << " not found\n"; return 0; }

**Output:**

search_element 4 found search_element 7 not found

In the above program, we have checked to cases and have used the default comparator. No need to mention, since this uses the binary search algorithm for searching, we need to feed sorted array only.

So as a pre-requisite we sorted the array. The sorted array is: **[1,2,3,4,5,6,7]**

Then for the first case, our range is the entire vector, and it returned true is since it finds the searched element **4**.

For the second case, our range is **[1-6]** as we mentioned the *end* iterator as *arr.begin()+arr.size()-1* which leaves the last element **7**. So searched element **7** is not found.

## 2) Using user-defined comparator function

Here we have taken a use case where we have student details for five students. By using the user-defined comparator we have checked whether there is a student with the specified marks or not.

#include <bits/stdc++.h> using namespace std; class student { int score; int roll; string name; public: student() { score = 0; roll = 0; name = ""; } student(int sc, int ro, string nm) { score = sc; roll = ro; name = nm; } int get_score() { return score; } int get_roll() { return roll; } string get_name() { return name; } }; //comparator for sorting bool myfunc(student a, student b) { if (a.get_score() < b.get_score()) //no swap return true; else //swap return false; } //comparator for binary search //match found if !mycomp(a,b) && !mycomp(b,a) bool mycomp(student a, student b) { if (a.get_score() < b.get_score()) return true; return false; } int main() { vector<student> arr(5); //1st student arr[0] = student(80, 5, "XYZ"); //roll 5, marks 80 //2nd student arr[1] = student(70, 10, "INC"); //roll 10, marks 70 //3rd student arr[2] = student(85, 7, "HYU"); //roll 7, marks 85 //4th student arr[3] = student(83, 1, "EFG"); //roll 1, marks 83 //5th student arr[4] = student(81, 11, "ABC"); //roll 11, marks 81 //sort based on marks //user-defined compartor=myfunc to sort sort(arr.begin(), arr.end(), myfunc); //find if any student exists who scored 81 student t1(81, -1, ""); //dummy search element just to search the student marks if (binary_search(arr.begin(), arr.end(), t1, mycomp)) cout << "Student with marks 81 exists\n"; else cout << "Student with marks 81 doesn't exist\n"; //find if any student exists who scored 75 student t2(75, -1, ""); //dummy search element just to search the student marks if (binary_search(arr.begin(), arr.end(), t2, mycomp)) cout << "Student with marks 75 exists\n"; else cout << "Student with marks 75 doesn't exist\n"; return 0; }

**Output:**

Student with marks 81 exists Student with marks 75 doesn't exist

Here we have first sorted the student vector using the user-defined comparator function. We have defined a separate comparator for binary search, though both have the same body. We have specified just to underline the factor that both comparators are not used in the same way. In case of searching, there is a match b/w *T a* and T b (T be the datatype) *if !comp(a,b) && !comp(b, a)* where *a* is element from the vector and *b* is the searching element.

So in this article, you saw how efficiently we can use *binary_search* to search elements within a range, no matter what kind of object it is. Even for the user-defined datatype, we can do by using a user-defined comparator as shown above. But, the main thing to remember is that the input list must be sorted(based on the key). For example, as we were searching for the marks, we sorted the student list based on marks.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.