Destopia's blog

Are all two pointers problems solvable with binary search?
By Destopia, history, 3 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like 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)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's your binary search alternative to Manacher's Algorithm for finding the longest palindromic substring?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Most of them, because binary search is also application of two pointers, i also used two pointers, l and r

→ Reply