rover1's blog

Strange thing happen in binary search?? PLEASE HELP!!
By rover1, history, 5 years ago, In English

Recently i was doing this (https://mirror.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://mirror.codeforces.com/contest/448/submission/7139620 what i have done is instead of writing l = x+1 i have written l=x Please HELP..

  • Vote: I like it
  • -14
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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:

L = 1, R = N
while L + 1 < R:
    m = (L + R) / 2
    if (a[m] == 0):
        L = m
    else:
        R = m

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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..

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply