arnav2004's blog

Mid calculated as low+((high-low+1)/2)
By arnav2004, history, 4 years ago, In English

I was recently solving this question using binary search(https://codeforces.net/problemset/problem/1201/C). I came to know about my mistake as my formula for calculating mid was low+(high-low)/2 but instead when I use low+(high-low+1)/2 I get AC.

My questions is when(and why) do we use low+(high-low+1)/2. I tried to google it and could not find any link which answers my question.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

In my implementation of binary search:

  • if the property holds for a suffix, and I want to find the leftmost element such that the property holds, I write this:
Code
  • if the property holds for a prefix, and I want to find the rightmost element such that the property holds, I write this (it's symmetric to the other case):
Code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you sir. Could you also tell me that why this condition holds true for a suffix and not for a prefix.

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

      Fixed, I swapped the two cases.
      By the way, the reason of WA in your code is while high-low>1: (because you can have low != high at the end of the binary search). You can notice that, if you replace that line with while high-low>0:, you get TLE. This is because the code can get stuck in an infinite loop in cases like low = 2, high = 3, mid = 2, low = mid = 2.
      Hence, you have to put mid = (low + high + 1) / 2 instead of mid = (low + high) / 2.

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

      Also, If you use while(low<=high)

      Then to avoid infinite loop use,

      if(can) low = mid+1;
else high = mid-1;
      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply