You are not logged in. Please login at www.codechef.com to post your questions!

×

STL (upper_bound and lower_bound)

1
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

asked 26 Oct '14, 15:23

dextrous's gravatar image

5★dextrous
1582210
accept rate: 0%

edited 26 Oct '14, 15:24


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.

link

answered 26 Oct '14, 15:46

michelangelo's gravatar image

4★michelangelo
1.1k21522
accept rate: 39%

edited 26 Oct '14, 15:58

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); ??

(26 Oct '14, 16:14) dextrous5★
1

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.

(26 Oct '14, 18:51) michelangelo4★

why subtract arr1 form lower_bound() ?

link

answered 31 May '17, 20:13

shashank0j's gravatar image

2★shashank0j
1
accept rate: 0%

1

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.

(31 May '17, 20:37) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×279

question asked: 26 Oct '14, 15:23

question was seen: 11,612 times

last updated: 31 May '17, 20:37