Binary Search With C++ STL

Problem Statement: Given a sorted array of size N, search for a given element in the array.

Examples:

Example 1: 

Input:
           N = 6
           Arr = {1, 4, 5, 6, 9, 9} 
           Element = 6

Output:
 True

Explanation:
 We can see 5 is present in the array at index 2.

Example 2:

Input: 
	   N = 6
           Arr[] = {1, 4, 5, 6, 9, 9} 
           Element = 7

Output:
 False

Explanation:
 We can see 7 is not present in the array, hence we return -1.

Solution :

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Solution 1:

Approach :

The low boundary is 0 and the high boundary is N-1. Why was it chosen so? Because our search space is the array given. We will update low and high in every iteration to reduce search space such that we get our target element if present. How to reduce search space?

Firstly we will find the midpoint of the given search space. Then check if the midpoint element is equal to the target element. If not, we will check whether the target element is greater than or less than the midpoint element. When the target is greater than elements, this indicates that we have to restrict our search space to the right. This can be done by updating low to midpoint+1. When the target is less than the midpoint element, we have to restrict search space to the left. This can be done by updating high to midpoint-1. When search space reduces to 0, which is when low is greater than high, searching stops.

This searching applies only when the array is sorted.

Dry Run :

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;

bool binarySearch(vector<int>& arr,int element) {
    int low = 0,high = arr.size()-1;
    while(low < high) {
        int mid = (low+high)/2;
        if(arr[mid] == element) return true;
        else if(element > arr[mid]) low = mid+1;
        else high = mid-1;
    }
    return false;
}

int main() {
    vector<int> arr = {1,4,5,6,9,9};
    int element = 6;
    
    if(binarySearch(arr,element)) cout<<”True”;
    else cout<<”False”;
    
    return 0;
}

Output: True

Time Complexity: O(logN)

Reason: For every iteration, search space reduces by 2. So, after kth iteration search space reduces to N/2k

N/2k = 1

N     = 2k

log2(N) = log2(2k)

log2(N) = klog2(2)  [log2(2) = 1]

log2(N) = k

This gives time complexity as log(N).

Space Complexity : O(1)

Reason: No extra data structure is used.

Solution 2 :

Approach :

We know the working of binary search. In C++, we have stl for binary search. It takes input as two iterators, each for the start and end of the array, and a target. It returns true if the element is present in the given array, else false.

Syntax :

bool res = binary_search(itr1,itr2,element)

Code :

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    vector<int> arr = {1,4,5,6,9,9};
    int element = 6;
    
    if(binary_search(arr.begin(),arr.end(),element)) cout<<"True";
    else cout<<"False";
    
    return 0;
}

Output: True

Time Complexity : O(logN)

Reason: stl function internally uses binary search only.

Space Complexity: O(1)

Reason: No extra data structure is used.

Some other stl functions on binary search:

  • Lower Bound

Operation :

It returns an iterator. If the element is present, returns an iterator for its first occurrence. If not, return the iterator for its next greater element in the array. When the element is not present in the array and greater than the largest element present in the array then the iterator returned is outside the array.

Syntax :

int* itr = lower_bound(itr1,itr2,element);//returning iterator

int index = lower_bound(itr1,itr2,element)-itr1;//returns index at which iterator is pointing

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    vector<int> arr = {1,4,5,6,9,9};
    int element = 9;
    
    vector<int>::iterator itr = lower_bound(arr.begin(),arr.end(),element);//returns iterator
    int index = lower_bound(arr.begin(),arr.end(),element)-arr.begin();//returns index
    
    cout<<"Iterator: "<<itr-arr.begin()<<" Index: "<<index;
    
    return 0;
}

Output: Iterator: 4 Index: 4

Time Complexity : O(logN)

Reason: It is based on binary search.

Space Complexity : O(1)

Reason: It is based on binary search.

  • Upper Bound

Operation :

It returns an iterator pointing next to the target element present or the next greater element in the array when the target is not present. If the target is greater than the largest element in the given array, it returns an iterator at the end of the array.

Syntax :

int* itr = upper_bound(itr1,itr2,target);//returning iterator

int index = upper_bound(itr1,itr2,target)-itr1;//returns index at which iterator is pointing

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main() {
    vector<int> arr = {1,4,5,6,9,9};
    int element = 9;
    
    vector<int>::iterator itr = upper_bound(arr.begin(),arr.end(),element);//returns iterator
    int index = upper_bound(arr.begin(),arr.end(),element)-arr.begin();//returns index
    
    cout<<"Iterator: "<<itr-arr.begin()<<" Index: "<<index;
    
    return 0;
}

Output: Iterator: 6 Index: 6

Time Complexity : O(logN)

Reason: It is based on binary search.

Space Complexity : O(1)

Reason: It is based on binary search.

Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article