Блог пользователя rover1

Strange thing happen in binary search?? PLEASE HELP!!
Автор rover1, история, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить