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

×

Can we do binary search on std::set?

I am looking for a custom binary search, not STL. How can we do the custom binary search on set?

asked 08 Jun '18, 14:31

vikram_91's gravatar image

3★vikram_91
213
accept rate: 0%

edited 08 Jun '18, 17:57

I have got a good website which can answer this question very appropriately. Please refer here , and then here

(08 Jun '18, 14:59) vijju123 ♦♦4★

First I tried google after that I have posted this question here because I didn't get anything relevant. I also tried binary search on set using std:: advance but std:: advance takes O(n) time in worst case on set.

(08 Jun '18, 15:12) vikram_913★

Its been asked in the forums. I remember giving a link to that in one of my editorials. lower_bound is the function you are looking for. Just be careful on which lower-bound. There are 2 versions, one is $O(N)$ other $O(LogN)$

(08 Jun '18, 15:17) vijju123 ♦♦4★

I know about lower_bound and upper_bound. I have used them many times. Here I have work which can be done using binary_search. And I am not sure if we can do binary search on set like we do a normal binary_search without c++ STL.

(08 Jun '18, 17:12) vikram_913★

Then thats the case of question being vague. Mention that you are looking for a custom binary search function and not STL ones like lower_bound. The only thing you asked is "Can we do binary search? If yes how?" the answer to which is STL lower_bound.

One of the reasons I dont favor one liner questions.

(08 Jun '18, 17:33) vijju123 ♦♦4★

I have edited the question. thanks

(08 Jun '18, 17:58) vikram_913★
showing 5 of 6 show all

Ofcourse you can do it i think this would work

int binary(int l,int r,int t)
{
      while(l < = r)
      {
           int mid=(l+r)/2;
           set<int> iterrator it= s.begin();
           advance(it,mid);
           if(*it==t)
           return mid;
           else if(*it > t)
           r=mid-1;
           else
           l=mid+1;
      }
   return -1;
}
link

answered 08 Jun '18, 15:04

ssp547's gravatar image

3★ssp547
3077
accept rate: 25%

edited 08 Jun '18, 18:17

No, we cannot do this.

it is a pointer and we cannot add or subtract from a pointer. We can increment or decrement it.

  set<int> iterrator it= s.begin()+mid;

we cannot do above part for set.

(08 Jun '18, 17:09) vikram_913★

oh sorry my bad! I forgot that generic iterators can't be added like that you can either use advance to increment it till mid but that would give you complexity O(nlogn) and one more option first copy the values of set in a vector and then do a normal binary search on the vector this would give you complexity O(n+logn) which would be better but keep in mind that you need to use extra space for that.I researched in google there is no other way. for the custom binary search. I edited my code according to stl advance function

(08 Jun '18, 18:16) ssp5473★

Thanks for your efforts. I tried std:: advance after that I posted this question here.

(08 Jun '18, 23:46) vikram_913★

Hmm what exactly is your purpose to do binary search. Why lower_bound() wouldn't work . Tell that exact purpose maybe we will be able to figure out even more efficient solution

(09 Jun '18, 00:25) ssp5473★

I cannot tell now, because I am using it in one of ongoing contest question. Maybe after the contest, we can try. Thanks

(09 Jun '18, 10:11) vikram_913★
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:

×1,038
×160

question asked: 08 Jun '18, 14:31

question was seen: 172 times

last updated: 09 Jun '18, 10:11