If you're looking for some binary search practice, this blog might be for you. I have compiled a list (I've heard lists are very popular on CodeForces) of some problems I really liked. The only criteria I used is that the solution for the problem has to be vaguely related to binary search. And I also tried to have some variety in the problems I chose, so they are not all the same type of application of binary search.
Here are 12 problems, in a roughly increasing order of difficulty, that are vaguely (or less vaguely) related to binary search:
- 1672E - notepad.exe
- Median of two sorted arrays Although the time limit doesn't enforce it, try to make a $$$O(log(n+m))$$$ solution.
- IOI 2013 Cave or if you prefer the Codeforces archive: IOI 2013 Cave
- IOI 2020 routers
- IX'th Problem from NWERC 2021
- Worm Worries BOI 2018
- IOI 2015 Scales. Codeforces archive link: IOI 2015 Scales
- Peer Streaming Spotify 2011
- 1028G - Guess the number
- Secret Sequence Swedish Coding Cup 2017
- IOI 2017 Prize. Codeforces archive link: IOI 2017 Prize
- 1483E - Vabank
It turns out the coolest uses (or variations) of binary search I know appeared in interactive problems, who would have guessed :)
Do you have curated problems like that in the other topics? if yes , could you please share it