HOW Can i binary search on a set?????

Блог пользователя Aly

Автор Aly, история, 9 месяцев назад, По-английски

set iterator is not like vector iterator i cant add to the iteratire so how can i do binary search on a set and how can i find the diffrence betwen two positions in a set

binary search, set, iterator, pointer

Aly
9 месяцев назад
13

Комментарии (13)

Написать комментарий?

Aly

9 месяцев назад, # |

Auto comment: topic has been updated by Aly (previous revision, new revision, compare).

→ Ответить

xruto

9 месяцев назад, # |

You can use : s.lower_bound(x) s.upper_bound(x)

→ Ответить

Aly

9 месяцев назад, # ^ |

thanks , but i want to find the index of the returned iterator from the function

→ Ответить

xruto

9 месяцев назад, # ^ |

← Rev. 2 →

+11

It's impossible ! :(

But you can use Ordered_Set

ref: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/

→ Ответить

monologue

9 месяцев назад, # ^ |

+10

Sounds like you need a self-balancing binary search tree. You can learn something about __gnu_pbds :: tree, which has implemented one.

→ Ответить

Aly

9 месяцев назад, # ^ |

thanks :)

→ Ответить

vishal2101

9 месяцев назад, # ^ |

-13

index can be find using distance of required iterator with the begin iterator, distance is present in c++ stl.

→ Ответить

RecursiveCo

9 месяцев назад, # ^ |

+13

That is O(n) if you use a set (or multiset, for that matter), since iterators work differently in those data structures. The reason it works in O(1) for a vector is that vectors have random-access iterators.

→ Ответить

Aly

9 месяцев назад, # ^ |

thanks :)

→ Ответить

MAX11189

9 месяцев назад, # |

← Rev. 2 →

lower_bound(k) //O(n)

s.lower_bound(k) //O(log n)

→ Ответить

Aly

9 месяцев назад, # ^ |

thanks :)

→ Ответить

Rafi

9 месяцев назад, # |

← Rev. 2 →

You can solve pbds if you are facing problem due to limitations in set and multiset. You can learn it from here: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/amp/

Make sure you are using c++20, because pbds use red-black tree and it applies operations in log(n) but it consumes slidely more time than set and multiset.C++20 is faster. So it should be preferred. You can see the blog to realise that: https://codeforces.com/blog/entry/113537

→ Ответить