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?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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?
Название |
---|
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.
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)
What's your binary search alternative to Manacher's Algorithm for finding the longest palindromic substring?
Forward and backward string hashes and binary search for longest length which they are equal at every position. Easier than Manacher's and also easily linear time if you just don't binary search and rather do a sliding window that you expand when possible at the cost of having some probability of failure
Most of them, because binary search is also application of two pointers, i also used two pointers, l and r