Sam_1812's blog

By Sam_1812, history, 19 months ago, In English

Hi guys. The question looks silly but i am able to recognize the binary search pattern in leetcode but I just cant figure out them while solving in CodeForces like the problem E. Building an Aquarium https://codeforces.me/problemset/problem/1873/E if anyone has faced such problem and has a solution it would be great to know and learn .

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
19 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

Binary search problems usually have two cases (searching for the answer itself, searching for a value that u need in an array), the second is quite easy and i don't think this is what ur question is about so let's talk about the first, binary search problems are mostly optimization problems so you need to either find the maximum or the minimum value to solve the problem, for binary search to work the answer must be increasing or decreasing which means that if u are searching for the maximum possible value that satisfies the conditions then for each (i <= ans) i must satisfy the condition, and the opposite is true that if u are searching for the minimum value that satisfies the condition therefore for each (i >= ans) i must satisfy the condition, now the only thing remaining is to know how u can validate if a value satisfies the condition for the problem, and that's it i guess this is everything to look into to define if a problem is a binary search problem or not.

»
19 months ago, hide # |
 
Vote: I like it -23 Vote: I do not like it

I wouldn't say it's binary search. There are 2 pointers, a modified binary search, and a greedy algorithm. How to recognize such problems: 1) No graph. So it's not Dijkstra. 2) No mention of "all possible" or "find the number of sets". So it's not combinatorics. 3) No work with subsets. So it's not bit masks or dynamics. 4) Not geometry — not geometry. 5) Not number theory. So it's not some divisions or very large numbers. 6) No ranges or queries. So it's not Fenwick or Segments, sorting segments, or schedule. 7) No "they add up to K" or "no more than K". So it's not dynamics or bit masks.

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

imagine a problem where we need the minimum number $$$x$$$ that is $$$good$$$, if all the numbers $$$ \gt x$$$ are good and all numbers $$$ \lt x$$$ are not, then this is usually binary search problem.

I recommend Errichto video explaining this point.