0

Are all two pointers problems solvable with binary search?

 8 months ago
source link: http://codeforces.com/blog/entry/102806
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

I've solved a lot of two pointers problems, I found that every problem I solved with two pointers is also solvable with binary search, is that true?

8 hours ago, # |

Two pointers is a very generic technique, and I am sure there are problems you can solve using two pointers but not binary search. For example, Mo's algorithm is in some sense an application of two pointers, but I don't see how someone could use binary search in it.

8 hours ago, # |

It isn't true, but the answer to that question isnt really thst important. Sets for example can solve everything a priority queue can, but people still use priority queues for a lot of problems.

Sometimes using binary search goes over the time limit, sometimes you would need an extra structure to use binary search, sometimes two pointers is more convinient to code.

Learn both and use them when necessary (even though i would say that binary search is more important)

95 minutes ago, # |

Rev. 2  

0

no because when using two pointers when you add one to one of the pointers only one element changes


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK