while using multiset of pairs in a question i got tle when i was searching a pair in multiset using binary_search function…but when i did the same using find function (in case of multiset) then i got the correct answer verdict without doing any further change in the two codes(one using binary_search and the other using find function)
…Can anyone please tell me why I am getting tle with binary_search and correct answer using find function in case of multiset ,as I think binary_search also takes log(N) time just like find function in sorted case…? Please help…
binary_search has a logarithmic time complexity only for LegacyRandomAccessIterators. This is the case of std::vector iterators, for example.
Sets/multisets are trees, so their iterators don’t allow random access. This makes binary_search run in linear time, which is significantly slower for a large range.
This is why std::set and std::multiset have a “find” function, while vector doesn’t. They need their own binary search implementation to be able to run in logarithmic time.
But the same problem done using binary search on set of pairs gave ac in just 0.34 seconds…while it crossed the time limit(2secs) using multiset…will there be so much of difderence using multiset?
Maybe your multiset has a lot more elements, because it has duplicates. I’m just trying to guess here. If you want to know for sure, you should share a link to the problem statement and both versions of your code.
Firstly the pairs given in the problem are distinct…but for more assistance i am sharing the problem statement link below
My solution link using multiset giving tle with binary serach is given below
https://www.codechef.com/viewsolution/23987497
My solution with multiset using find function giving AC is given below
https://www.codechef.com/viewsolution/23987510
Secondly for your ease…I wanna tell you that the input will be pairwise distinct as all the input is containg different rows and columns in the question…please reply ASAP…
This is not what you described. You said “binary search on set of pairs gave ac”.
I checked out all your submissions for this problem, you have no submission with binary_search on a set of pairs that gives AC.
So could you rephrase what it is that you don’t understand?
Really sorry for deviating you from my actual topic sir,
My question is that why binary_search function is giving tle using multiset while find function is giving an AC
No worries.
This is what I explained in my first message: binary_search doesn’t work well with set/multiset iterators, because they don’t allow random access.
For instance, if your range spans over 1000 elements, binary_search will want to look at the element at pos 500 first. Vector iterators are more or less pointers, it’s easy to do begin + 500 with pointer arithmetics. Since the elements are sorted, we can remove half of the range with a single comparison. That’s why binary_search is very efficient, with logarithmic complexity.
In a set or multiset, nodes that are neighors in the tree are not necessarily neighbors in memory.
binary_search would not even be able to know how many elements are in the range, end - begin is not supported. So the search starts at begin the iterator is incremented, until it reaches a value not lower than the one we are searching for.
This is why binary_search has poor performance with sets, and you should use the find function provided by the container, that has a more suitable search strategy.
Thankyou so much for explaining me this topic so well sir…if you dont mind can i get ur email so that i can ask u doubts in future if u dont have any problem sir…i am a first year college student and dont know much in competitive programming so i need a good assistance from someone who is already a master of thsi field…please can you help me sir .
Sir if this is the reason for multiset…then set is also implemented as tree then why binary serach is working in it
…i am sharing my frnds solution in which he did the sam eusjng set of pairs and binary search…then tell how did that got AC if it is also a tree…
Here the set solution…
https://www.codechef.com/viewsolution/23992234
You’re welcome! I’m also a student, you don’t have to call me sir. 
And I’m not a master in this field, still learning too. Frankly I don’t have time to tutor someone, I’m sure you will get answers if you keep posting on this forum. 
Concerning your friend’s solution, he’s not using binary_search, he’s using find.
thanx bro… got it… by the way can u tell me how to start learning data structures and from where…
I have no idea, I learned programming at school. You should keep training, and check out the editorials when you can’t solve a problem, that’s how I learn.