vikalp14's blog

By vikalp14, history, 3 weeks 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  

»
3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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 ?

    • »
      »
      »
      3 weeks 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].

    • »
      »
      »
      3 weeks 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 :)

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Hmm for such case (i.e. when l==r-1) we have only two values in the search space so we have to compute the function for both values. Thanks this discussion helped me a lot :)

»
3 weeks 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.