vikalp14's blog

Is this binary search implementation reliable?
By vikalp14, history, 6 years ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

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

    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 ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

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

      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 :)

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

        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

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

          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.

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

            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?

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

              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.

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

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.

→ Reply