Lower_bound stl

#1

#include
#include
using namespace std;

int main() {

int arr[] = {10, 20, 30, 40, 50}; // work in the sort arrays only
int n = sizeof(arr) / sizeof(arr[0]);

// Sort functions
// sort(arr, arr + n);

// for (int i = 0; i < n; i++) {
// 	cout << arr[i] << " ";
// }


// lower_bound and mainly used in the frequency count
auto it = lower_bound(arr, arr + n, 31);
cout << it - arr;

return 0;

}
why its returning the 40 index. I want to get the index of that element which is smaller and equal to 31

#2

@Vikaspal lower_bound returns the index of the first index that is “greater than or equal to the key” in this case that element is 40. 30 is not greater than or equal to 31.
If you want the first element SMALLER than 31, do this, cout << it - arr -1;

#3

@Ishitagambhir but it make our custom compare function and return a<=b so it will give the less element or can say lower bound right?
30<=31

#4

@Vikaspal please watch the video again, thats not what happens

#5

lower_bound returns an iterator pointing to the first element in the range [first,last) which has a value not less than ‘val’.

upper_bound returns an iterator pointing to the first element in the range [first,last) which has a value greater than ‘val’.

#6

@Ishitagambhir i think ur not able to get my point.
let says we have int a[] = {1, 2, 5, 10, 20, 500, 100, 200, 500, 2000};
and i need to find the lb put the current lower bound function gives us >= means if key = 100, and if it present in the arrays it will return the address and we minust the base address to get the index right.
and in other case let se 120 so it will return the value is first greater value in the arrays right.
But if change our compare function to return a<=b, so in first case if 100 is present in the arrays it will return the address by is not present then it will lesser element in tha arrays like say for 120 as 120 not present so it should return the less value than 120 means 100.

But for the correct answer using the subtracting one index ?
Why not the above is correct.

#7

@Vikaspal

if you use this compare function, it will act like the upper_bound function, which returns the value of first element strictly greater than they key you provided. In the example you said your key is 120, so it will return 200 as 200 is the first element strictly greater than 120. Even if 120 was present in the array, it’d still return 200 because of the condition, “strictly greater than” .

#8

@Ishitagambhir okay then for the lower_bound default condition is a>=b , so we can only this two one or a < b b > a also works here.

#9

And also as this based on binary search half or the element is going to discard on starting like. from mid can please dry using small input so i have better understanding how the comparator is working internal and i make changes according to need.

#10

@Vikaspal i am not getting which dry run do you want? You can print values inside the compare function to see which values are getting compared and how.

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.