C++ lower_bound(), upper_bound(), binary_search()

                     

                                                                                   First i'll start with standard template library function binary_search(), this function basically return true or false. it takes the array & element to search as parameter and returns true or false if it's present or not in the array. See the following code.

binary_search()

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int x;
    cout << "Enter the element: " << endl;
    cin >> x;
    if (binary_search(A, A+10, x)){
        cout << "Element is present" << endl;
    } else {
        cout << "Element is not present" << endl;
    }
    return 0;
}

output of the above program on providing following inputs

Enter the element:
4
Element is present

Now as we provided 4 to search and as it's already present in the array .. the answer was as expected! Element is present. Now what if we provide 11 as input which is not present in the array. Let's see the output!

Enter the element:
11
Element is not present

And as expected 11 is not present in the array so the output of the program is Element is not present!

                                                                               binary_search() function is good if we wanna confirm if element is present in the array or not ... but what if we wanna know the index at which the element is present or if it's not persent then the index of the next element. This functionality can be accomplished using STL's lower_bound() & upper_bound().  So let's take lower_bound() next!

lower_bound()

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    vector<int> A = {1, 2, 3, 4, 6, 7, 8, 9, 10};
    vector<int>::iterator lower;
    int x;
    cout << "Enter the value of x: " << endl;
    cin >> x;
    lower = lower_bound(A.begin(), A.end(), x);
    cout << lower - A.begin() << "\n";
    return 0;
}

Now as you can see we have a sorted vector here, let's get the index of the element which is already present in the vector.

Enter the value of x:
2
1

The index of element 2 is 1 and that is correct! Now let's search for 5 which is not present in the vector.

Enter the value of x:
5
4

And it returned 4 as index for element 5. but as you see vector element 5 is not present! The beauty of this function is that it doesn't show any error it's returns the index of the element which is just bigger then it. Now let's take some cases.

1st case.)  we provide a value which is not present in the vector and is greater then all the elements

Enter the value of x:
121
9

So it adds +1 in the last index and returns it.

2nd case.) we provide a value which is not present in the vector and is smaller then all the elements

Enter the value of x:
-121
0

So it returns the starting index i.e. 0


3rd case.) we provide a vector which has many duplicate values like [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

Enter the value of x:
5
4

So it returns the first occurence of the element. The element 5 is present at indexes 4, 5, 6. and the lower_bound() functions returns it's lower index or first occurence!

upper_bound()

Now let me add some code for upper_bound() function

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    vector<int> A = {1, 2, 3, 4, 6, 7, 8, 9, 10};
    vector<int>::iterator upper;
    int x;
    cout << "Enter the value of x: " << endl;
    cin >> x;
    upper = upper_bound(A.begin(), A.end(), x);
    cout << upper - A.begin() << "\n";
    return 0;
}

Now as we have a sorted vector here let's search for an element which is already present in the vector!

Enter the value of x:
2
2

The index returned here by the upper_bound() function is +1 of the original index!

Now let's search for 5 which is not present in the vector!

Enter the value of x:
5
4

And the result here is same as lower_bound. if upper_bound() doesn't find the value then it just returns the index of next greater index!

now let's take some cases here

1st case.) We provide an element which is not present in the vector and is greater then all the elements in the vector!

Enter the value of x:
121
9

Same result as lower_bound(), when it doesn't find the element and all elements are smaller then the element to be found then it returns index + 1 of the last index of the vector

2nd case.) We provide an element which is not present in the vector and is smaller then all elements in the vector!

Enter the value of x:
-121
-121
0

Now this is also same as lower_bound(), when the element we wanna found in smaller the then smallest element of the vector then it returns the index 0.

3rd case.) We provide a vector which has many duplicate values like this [1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 9]

Enter the value of x:
5
7

And this isn't similar to lower_bound(). lower_bound() was returning 4, which is the index of first occurence of element 5. But upper_bound() returns index of last occurence of element + 1


                                                                          That's it! Thanks for your patience!