I want to solve this problem 1175C -Electrification , using binary search but got stucked . I checked many code of red coders whom used binary search . But it is hard to guess the logic from code . Can anyone explain what is the binary search approach ?
I tried myself using binary search . My approach was: just pick an mid , f2(mid) <= f2(mid+1) that means all values from mid+1 to high are greater , so high=mid . Else low=mid;
Here f2(x) function takes a value and push all abs(ar[i]-x) to vector then sort it and return kth value [hence i used 0 based index] .
This code fails when f2(mid)==f2(mid+1) .
**my code**
You can use ternary search, here
If $$$f_k(x)$$$ is actually strictly decreasing, then strictly increasing, as you say in your drawing, then you could use ternary search to solve this problem. The problem is that I do not think that $$$f_k(x)$$$ actually is strictly decreasing, then strictly increasing. I think it could have multiple local minimums, some of which may not be the global minimum. For example, try to draw the graph for $$$f_k(x)$$$ on the following test case:
On the other hand, Smaug did use binary search to solve the problem and they got accepted, so let's examine what they did.
First, notice that if you have $$$k+1$$$ continuous elements $$$a_i, a_{i+1}, a_{i+2}, ..., a_{i+k}$$$, then there exists some $$$x \in [a_i, a_{i+k}]$$$ such that $$$f_k(x) \leq \lceil \frac{a_{i+k}-a_i}{2} \rceil$$$. This is because for any $$$x$$$ in this interval, the $$$k+1^{\text{th}}$$$ smallest distance will either be the distance between $$$x$$$ and $$$a_i$$$ or the distance between $$$x$$$ and $$$a_{i+k}$$$, so the best way to minimize $$$f_k(x)$$$ is to put $$$x$$$ halfway in between $$$a_i$$$ and $$$a_{i+k}$$$.
Now, let's say we guess that the minimum value of $$$f_k(x)$$$ is $$$M$$$. From the above, it is pretty easy to check if $$$f_k(x)=M$$$ is a possibility: If there exists some $$$i$$$ such that $$$M \leq \lceil \frac{a_{i+k}-a_i}{2} \rceil$$$, then $$$M$$$ is a possible answer, but it might not be the minimum value, so we need to guess lower. Otherwise, if there is no such $$$i$$$ for which the inequality holds, then $$$M$$$ is too small and we need to guess higher.
This is how Smaug uses binary search to find the minimum value of $$$f_k(x)$$$: First, they set up a
bool check(long long M)function which verifies that $$$M$$$ is a possible answer. Then, in their binary search, they always guess $$$M=\frac{L+R}{2}$$$, where $$$L$$$ and $$$R$$$ are the minimum and maximum values, respectively, in the binary search. Ifcheck(M)returnstrue, they setR = Mso that the next guess will be lower. Otherwise, they setL = Mso that the next guess will be higher. When the binary search is finished, we know that $$$R$$$ is the lowest possible value of $$$f_k(x)$$$Finally, after the binary search, once they know what the minimum value of $$$f_k(x)$$$ is, they do one last pass through the array in order to find the corresponding $$$x$$$-value, which is the final answer.
Hopefully, this helps explain how binary search can be used to solve this problem. Of course, binary search is not necessary and it could be solved by instead finding the minimum possible value of $$$\lceil \frac{a_i+a_{i+k}}{2} \rceil$$$ in one
forloop, but binary search is still a valid solution even if it may not be needed. If you have any questions, feel free to ask in a comment below.