STL (upper_bound and lower_bound)

general
1

I want to know how to use these STL functions.

for example in the question CSS2 (LTIME17) ,i calculated upper bound and lower bound modifying the binary search code(myself). but i want to know that how can i use these inbuilt functions to save time .

link to my accepted solution - http://www.codechef.com/viewsolution/5225565 .

But on using these functions I am getting an error on ideone - http://ideone.com/wuLk1P

1 Like
2

If the name of the array is arr1, then you can use it like this:

l1=lower___bound(arr1,arr1+n,w)-arr1;

Similarly for upper bound just subtract the name of the array from the function.

If n=5, arr1[]={1,2,4,5,6} and if you search for 3 with l1=lower_bound(arr1,arr1+n,3)-arr1; then value of l1 will be 2, that is if the element is not present in the array it returns the index where the number should have been present. So, you’ll have to check if(arr1[l1]==3) or not to know whether the element is present or absent.

3 Likes
3

what about l4?
do i have to write l4=upper_bound(arr2+l1,arr2+l2,e)-arr2; or l4=upper_bound(arr2+l1,arr2+l2,e)-(arr2+l1); ??

4

You have to use l4=upper_bound(arr2+l1,arr2+l2,e)-arr2; but the value will be stored at name[l4-1].val. Remember that you always have to subtract the array name from upperbound and lowerbound when using arrays.

1 Like
5

why subtract arr1 form lower_bound()
?

6

Because lower_bound() returns an iterator, and not an index. Refer to the documentation for details. You can consider it to be a pointer here, so the difference between the iterator and the address of the first element gives you the required index.

1 Like