Implementing Upper Bound and Lower Bound from Binary Search

Introduction

Prerequisites : Binary Search Algorithm (Sorting and Searching

Referencce : Everything you need to know about Binary Search algorithm — Jorge Chávez (jorgechavez.dev)

We already have inbuilt STL functions in C++ for performing upper-bounds and lower bounds operations on vectors.

GeeksForGeeks define upper and lower bounds as:

• The upper_bound() is a built-in function in C++ STL which returns an iterator pointing to the immediate next element which is just greater than k. If the key passed in the parameter exceeds the maximum key in the container, then the iterator returned points to next of last element (which can be identified using set end() function) in the set container.
• The lower_bound() method in C++ is used to return an iterator pointing to the first element in the range [first, last) which has a value not less than val. This means that the function returns the index of the next smallest number just greater than or equal to that number. If there are multiple values that are equal to val, lower_bound() returns the index of the first such value.

In short we can say that for an element k, upper_bound returns first element in the sorted vector such that it is strictly greater than the element k, while the lower_bound returns the first element in the sorted vector which is just greater than or equal to the element k.

If the element k is not present in the vector, upper_bound and lower_bound returns the same result. WHY ??

This GFG Article gives the STL implementation of both bounds.

The reason you are here :-)

In this article I will be discussing the implementations of both upper and lower bounds from scratch (using binary search algorithm).

1. UpperBound implementation from Binary Search

We will be implementing simple Binary search code. As we have to find the smallest element that is strictly greater than the element k, so every-time we find an element strictly greater than the element k, only than we update our ans to mid and make high = mid-1. Else we update low = mid+1. We keep doing this unless low becomes greater than high, and when it happens we have got our answer stored at ans index.

int findUpperBound(vector<int> vec, int k){
    int low = 0;
    int high = vec.size()-1;
    // ans stores Index of element which is upper bound of k
    int ans = -1;   
    
    while(low <= high){
        
        int mid = low + (high - low) / 2;
        if(vec[mid] <= k){
            low = mid+1;
        }
        else{
            ans = mid;
            high = mid-1;
        }
    }
    // return only ans if you want just the index of upper-bound
    return vec[ans]; 
}

2. LowerBound implementation from Binary Search

Similarly here also we will be implementing simple Binary search code. In this case we have to find the first element greater than or equal than the element k, so every-time we find an element that is greater than or equal to the element k, only than we update our ans to mid and make low= mid+1. Else we update high = mid-1. We keep doing this unless low becomes greater than high, and when it happens we have got our answer stored at ans+1 index.

Why in this case we have our answer at ans+1 index not ans index ?
It is so because here the ans index stores the index that contains the greatest element that is strictly smaller than our value k, but for lower bound we need the value just greater than or equal to k hence we return ans+1 index and not ans.

int findLowerBound(vector<int> vec, int k){
    int low = 0;
    int high = vec.size()-1;
    // ans will store the prev index of element which is the lower bound of k
    int ans = -1;  
    
    while(low <= high){
        
        int mid = low + (high - low) / 2;
        if(vec[mid] >=k){
            high = mid-1;
        }
        else{
            ans = mid;
            low = mid+1;
        }
    }
     // return only ans+1 if you want just the index of lower-bound
     return vec[ans+1];
}

Thank you !

Reference : GeeksForGeeks