Recently i was doing this (https://codeforces.com/contest/448/problem/D) question and got stuck when my solution goes in infinite loop then i see the correct solution and notice the difference and dry run my code, then i realize my code is incorrect. Now i want to know why this happen.. link to correct solution -- https://codeforces.com/contest/448/submission/7139620 what i have done is instead of writing l = x+1 i have written l=x Please HELP..
Binary search is algorithm that can find position where $$$0$$$ change to $$$1$$$ in array $$$[0, 0, \ldots , 0, 1, 1, \ldots 1]$$$. So let $$$L$$$ always be position with $$$0$$$, and $$$R$$$ — position with $$$1$$$. Binary search will look very simple:
Sometimes array has not any $$$0$$$ or $$$1$$$. So let $$$a[0] = 0; a[N + 1] = 1$$$ and $$$L = 0, R = N + 1$$$. Similar logic can solve you problem.
Thanks for explaining but how we know that when we do l=mid and when l=mid+1.. Is there ant trick or mathematically proof or it depends on observation... Please help, I'm very comfusing about this. thanks..
Very simple — always using $$$L = mid$$$. Because every discrete binsearch, in fact, is equivalent to the one I desribed. For example, in sorting array $$$A$$$ you have to find first element, not less than $$$a$$$ (lower_bound). Let $$$B_i = (A_i >= a)$$$. Then you have to find border between $$$0$$$ and $$$1$$$ in array $$$B$$$.
Even I used to have that confusion,if you are taking mid=(l+r)/2,take low=mid+1,if you are taking mid =(l+r+1)/2,take low =mid
If the range of binary search is [l, r], you can avoid infinite loop: just finish the binary search when r-l < 1, (when range has length 2 or less). Then, you can test this two values after binary search, which doesn't affect the complexity.