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

Is this binary search implementation reliable?
Автор vikalp14, история, 6 лет назад, По-английски

Hey I found this implementation on a codeforces blog. What do you think about it , is this the most easy and reliable implementation according to you (for solving the problems)? I am asking because there's so much confusing stuff about loop invariants and I just want something which always works for sure!

l, r = -1, n
while r-l > 1:
    m = (l+r)//2
    if F(a[m]):
        l = m
    else:
        r = m

You can easily prove that l = k and r = k + 1 by the end of the while loop. In this case no worries about whether to increase m by 1 or not.

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

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Yes, it is very easy implementation and it can be used, in cycle m can get values only from 0 to n - 1, it has not yet failed me. For example, this problem and solution using binary search.

UPD: And in this problem too

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

Reliable? Yes.

Easy? Depends on whether you like [l, r] or [l, r). Personally I prefer [l, r] implementations over this, it's easier to do / think about.

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

    If we know the range then any implementation can be used right? For example: if answer lies in [l,r) then the above implementation can be used with l=l-1 and r=r ?

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

      The above implementation is [l, r), and that is perfectly fine.

      I am just stating a matter of preference, because I make less bugs when I use [l, r].

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

      I think it's even simpler than that. After the "while" loop you know that correct answer is either "l" or "r" so you can check both by calling function "F" on them again and take smaller/larger (depending on what problem is asking for). I've seen that in codes of some really good coders.

      Personally I don't like that approach, but who cares. If it works for you then, well... it works for you :)

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

        Oh you so have to check the l(or r) at last...I haven't encountered a problem yet where the ans doesn't lies in the search space hence was not doing that! Thanks

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

          No, I'm not talking about that. You are left with 2 values, "l" and "r", so you don't know the exact solution (is it "l" or "r"). Therefore you have to calculate "F" again for both of them.

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

            I thought if the answer lies to left of mid then it should be 'l' but if the answer lies to right then it should be 'r'. The given implementation thus can give l,r == k,k+1 or l,r==K+1,k where k is the point where the function changes.

            So if we always shrink the search space to the right of mid then the answer should be in 'r' (similarly for 'l')

            I don't understand when it gives confusing answer, can you give a example of such a case?

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

              Sorry, I was wrong. Only case when it's like that is when you have l == r — 1 at the start, but that's just some corner case.

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

no worries about whether to increase m by 1 or not

I can tell how I do the +-1 stuff. I think it is easy.

For example if we want to find biggest element in an array, that is not bigger than val. max{arr[i] so that arr[i]<=val} Array is sorted in increasing order. So some(maybe 0) first elements are less than val. Next some(maybe 0) numbers are equal to val. And last some(maybe 0) elements are bigger than val. Now we draw this "picture"

<<<<<=====>>>>>>

if arr[m]>val than arr[m] and elements righter than m are not <=val(we look at the "picture")
<<<<<=====>> **>** >>>
[l;r] -> [l;m-1]

if arr[m]<=val than m and elements lefter than m are <=val. So they can be the answer.(we look at the "picture")
<<<<**<=**====>>>>>>
[l;r] -> [m;r]

If we have some boolean function F(x) than the picture will look like this
++++++-------

Good luck! I hope this helps.

→ Ответить