Can we do binary search on std::set?

general
,
1

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

2

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

3

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;
}
1 Like
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.

5

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)

6

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.

7

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.

8

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.

9

I have edited the question. thanks

10

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

11

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

12

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

13

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