2020's blog

binary search (l+r)/2 or (l+r+1)/2 , not a random choice?
By 2020, history, 5 years ago, In English

binary search (l+r)/2 or (l+r+1)/2 i saw this on a topcoder article that one or the other will no give while loop but on some test cases both might not as can be seen in submission 76258234 is where i changed (r+l)/2 to r+l+1/2 from this submission 76258059 and my solution passed so how to decide which one will never give a while loop right now i just do it randomly one and if that doesnt pass i do other

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

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

Auto comment: topic has been updated by 2020 (previous revision, new revision, compare).

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

If your binary search is like this:

if(something) hi = mid;

else lo = mid + 1;

then it should be (lo + hi) / 2, and otherwise (lo = mid or hi = mid – 1) it should be (lo + hi + 1) / 2.

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

    from where you learned this trick, I was also confused between them

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

      Before I discovered that, I always used (lo + hi) / 2 and added some ifs to prevent TLE. Later, I found out I can just use (lo + hi + 1) instead.

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

    be careful on negative borders. if your condition is while(lo < hi) it can be looped

    just mid = (lo + hi) >> 1

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

I check for case r = l + 1 to decide

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

    Not sure why this is so downvoted. Understanding invariants and all is of course good, but I often just consider the case L = 0, R = 1 to choose between (L+R)/2 or (L+R+1)/2 – it's faster :)

    Another ugly method I sometimes (shamefully) use – just write (L+R)/2, if the program doesn't terminate, change it to (L+R+1)/2. :D
    Don't use this, no guarantees, etc.

    → Reply
»
5 years ago, # |
← Rev. 9   Vote: I like it +78 Vote: I do not like it

Suppose you have a predicate $$$P(n)$$$ which goes from being false to being true as $$$n$$$ increases, and you want to find the least $$$n$$$ for which it is true. There are two things to remember so you never get a binary search wrong:

1) Remember the invariant you are maintaining! At the end, you'll have $$$l = r$$$, $$$P(l-1)$$$ false and $$$P(l)$$$ true, so a good invariant is to say that $$$P(l-1)$$$ should always be false and $$$P(r)$$$ should always be true. With this, you can initialize the variables appropriately. Now let's look at the iteration steps:

while (l < r) {
    int mid = (l+r)/2;
    if (P(mid)) 
        r = mid; // Note that P(r) = P(mid) is true, so the invariant is maintained.  
    else
        l = mid+1; // Note that P(l-1) = P(mid+1-1) is false, so the invariant is maintained.
}

2) Both updates must decrease the length of the interval $$$[l, r]$$$, and we must round up or down to ensure that. Let's check the above code is correct: Since $$$l < r$$$, we have that (as real numbers) $$$l < \frac{l+r}{2} < r$$$, and therefore l <= (l+r)/2 < r after rounding down. Therefore, r = mid decreases $$$r$$$ and l = mid+1 increases $$$l$$$.

Let's do the same for a predicate $$$P(n)$$$ that goes from being true to being false as $$$n$$$ increases. Suppose we want to find the largest $$$n$$$ for which $$$P(n)$$$ is true. Then at the end, we will have $$$l = r$$$, $$$P(l)$$$ true and $$$P(l+1)$$$ false. Therefore, the invariant we will maintain is that $$$P(l)$$$ should always be true and $$$P(r+1)$$$ should always be false. How does the code look like in this case?

while (l < r) {
    int mid = ????;
    if (P(mid)) 
        l = mid; // Note that P(l) = P(mid) is true, so the invariant is maintained.
    else
        r = mid-1; // Note that P(r+1) = P(mid-1+1) is false, so the invariant is maintained.  
}

Now, it is still true that (as real numbers) $$$l < \frac{l+r}{2} < r$$$. But if we want l = mid to increase $$$l$$$, then we cannot round the division down. Rounding it up (by doing (l+r+1)/2) is fine, because then l < (l+r+1)/2 <= r, and therefore r = mid - 1 decreases $$$r$$$ and l = mid increases $$$l$$$.

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

    thanks man that was really good

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

    if I use 

    while (l <= r)
{
    int mid = l + (r &mdash; l) / 2;
    if (P(mid))
         l = ???;
    else
         r = ???;
}

    then l = mid + 1 and r = mid - 1 right ?

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

    I absolutely don't understand why you don't use binsearch, that ends with $$$l + 1 = r$$$. In this case invariant will be easier: $$$P(l)$$$ always be false and $$$P(r)$$$ always be true.

    So, the second thing is not necessary — if $$$r - l > 1$$$, then $$$l < \left \lfloor \frac{l + r}{2} \right \rfloor \leq \left \lceil \frac{l + r}{2} \right \rceil < r$$$ and length of the interval will decreases anyway. Thus you can use whatever you want — both formulas will work.

    Code looks like this:

    while (l + 1 < r) {
    int mid = (l + r) / 2;
    // int mid = (l + r + 1) / 2; // Will work too.
    if (P(mid))
        r = mid; // Note that P(r) is true.
    else
        l = mid; // Note that P(l) is false. Don't think about +-1.
}

    But you have to think about $$$l$$$ and $$$r$$$ at start. Often it is enough to set $$$l = -1$$$ and $$$r = n$$$ if you use binserch to find in array with indexes $$$[0 \ldots n - 1]$$$.

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

Normally, if the smaller l is, the more possible check(mid) will be true, use (l+r+1)/2. Otherwise, use (l+r)/2.

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

https://codeforces.me/blog/entry/67509

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

Btw, I see so many website use mid = low + (high — low) / 2. So how it differ from mid = (low + high) / 2 ?

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

    To prevent overflow. (low + high) is computed before dividing by 2 so may cause overflow.

    → Reply