# Binary Search functions in C++ STL (binary_search, lower_bound and upper_bound)

• Difficulty Level : Easy
• Last Updated : 22 Aug, 2022

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:

1. finding an element
2. lower_bound
3. upper_bound

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

## CPP

 `// C++ code to demonstrate the working of binary_search()` `#include ``using` `namespace` `std;` `// Driver's code``int` `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;``}`

Output

```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)

## 2. lower_bound:

lower_bound(start_ptr, end_ptr, num): Returns pointer to the position of num if the container contains only one occurrence of num. Returns a pointer to the first position of num if the container contains multiple occurrences of num. 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. 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.

## CPP

 `// C++ code to demonstrate the working of lower_bound()``#include ``using` `namespace` `std;` `// Driver's code``int` `main()``{``    ``// initializing vector of integers``    ``// for single occurrence``    ``vector<``int``> arr1 = { 10, 15, 20, 25, 30, 35 };` `    ``// initializing vector of integers``    ``// for multiple occurrences``    ``vector<``int``> arr2 = { 10, 15, 20, 20, 25, 30, 35 };` `    ``// initializing vector of integers``    ``// for no occurrence``    ``vector<``int``> arr3 = { 10, 15, 25, 30, 35 };` `    ``// using lower_bound() to check if 20 exists``    ``// single occurrence``    ``// prints 2``    ``cout << ``"The position of 20 using lower_bound "``            ``" (in single occurrence case) : "``;``    ``cout << lower_bound(arr1.begin(), arr1.end(), 20)``                ``- arr1.begin();` `    ``cout << endl;` `    ``// using lower_bound() to check if 20 exists``    ``// multiple occurrence``    ``// prints 2``    ``cout << ``"The position of 20 using lower_bound "``            ``"(in multiple occurrence case) : "``;``    ``cout << lower_bound(arr2.begin(), arr2.end(), 20)``                ``- arr2.begin();` `    ``cout << endl;` `    ``// using lower_bound() to check if 20 exists``    ``// no occurrence``    ``// prints 2 ( index of next higher)``    ``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
```

Time Complexity: O(log N) – where N is the number of elements in the array.
Auxiliary Space: O(1)

## 3. upper_bound:

upper_bound(start_ptr, end_ptr, num): Returns pointer to the position of next higher number than num if the container contains one occurrence of num. 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. 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. 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.

## CPP

 `// C++ code to demonstrate the working of upper_bound()``#include ``using` `namespace` `std;` `// Driver's code``int` `main()``{``    ``// initializing vector of integers``    ``// for single occurrence``    ``vector<``int``> arr1 = { 10, 15, 20, 25, 30, 35 };` `    ``// initializing vector of integers``    ``// for multiple occurrences``    ``vector<``int``> arr2 = { 10, 15, 20, 20, 25, 30, 35 };` `    ``// initializing vector of integers``    ``// for no occurrence``    ``vector<``int``> arr3 = { 10, 15, 25, 30, 35 };` `    ``// using upper_bound() to check if 20 exists``    ``// single occurrence``    ``// prints 3``    ``cout << ``"The position of 20 using upper_bound"``            ``" (in single occurrence case) : "``;``    ``cout << upper_bound(arr1.begin(), arr1.end(), 20)``                ``- arr1.begin();` `    ``cout << endl;` `    ``// using upper_bound() to check if 20 exists``    ``// multiple occurrence``    ``// prints 4``    ``cout << ``"The position of 20 using upper_bound "``            ``"(in multiple occurrence case) : "``;``    ``cout << upper_bound(arr2.begin(), arr2.end(), 20)``                ``- arr2.begin();` `    ``cout << endl;` `    ``// using upper_bound() to check if 20 exists``    ``// no occurrence``    ``// prints 2 ( index of next higher)``    ``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
```

Time Complexity: O(log N) – where N is the number of elements in the array.
Auxiliary Space: O(1)

This article is contributed by Manjeet Singh(HBD.N). If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

My Personal Notes arrow_drop_up