solve more problems, work on more ideas, see the editorial. after some months you will be able to identify it.

You should read about monotonic functions and try to find patterns similar to it. Also finding minimum or maximum value type problems may involve binary search on answer.

Tbh I still couldn't identify Binary search. My entire intuition of bs is "if it looks like dp, but constraints do not support dp and couldn't prove greedy then it must be binary search" and it works almost all the time.

If some function is monotonic and you want to know the equal range of some value you should use binary search.

Why would you try to identify a problem is binary search or not? Just be ready to apply binary search whenever you noticed such a function.

I apply binary search when i notice a pattern of TT..TF..FF or F..FTT..T .

One trick you can find in some problems is trying to find a number (often the minimum or the maximum) that works for a certain dataset, and you can verify if a certain number works in O(1) or O(n) (or different depending on the problem and input size).

I'll use this leetcode problem as an example.

You can verify if a certain amount of seconds works with an O(n) operation, and since the function is monotonic, you can simply search for the minimum value that works and return that.

(this doesn't apply to all problems, but it should hopefully be helpful)

Binary Search works when a function $$$f$$$ is increasing/decreasing (sorted in increasing/decreasing way) on $$$\mathbb{R}$$$ in general case , so if you've a computational complexity of $$$\mathcal{O}(f')$$$ for $$$f$$$ then you can apply binary search on $$$\mathcal{O}(f' \times \log(|r-l|)$$$ that's we apply binary search on range $$$[l,r]$$$.

However in some case this defintion can be optimized by some optimizations such as precalculation , for example :

Given an array $$$a$$$ of $$$a_1,a_2,..,a_n$$$ , find any subarray of sum $$$x$$$

Example 2

if there is a point where over it a constraint is met and under it a constraint is not met and you want to find the point its bs so the easiest version of this is searching a sorted array for x if md<x that is a constraint that is met and if x<=md that is constraint is not met

Boshkaskh Ma7foz

I used to struggle with this exact situation. And now I made a thumb rule, that if I don't get the idea of the problem maybe within 5-10 minutes. I try to finding if I can apply binary search the answer in some way. This helped me a lot, as sometimes it unexpectedly hit me where the solution was not very obvious.

And usually, there are two things to address when searching for the solution: 1. Can you reduce your search space drastically if you can verify that a given k works for you. 2. Is checking for a given k can be done in O(n) or O(n logn) or anything below O(n^2). Although, it highly depends on the context of the problem, but this is a good point to think.

I hope this help you in some way.