| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
I was recently solving this question using binary search(https://codeforces.me/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.
Auto comment: topic has been updated by arnav2004 (previous revision, new revision, compare).
In my implementation of binary search:
Thank you sir. Could you also tell me that why this condition holds true for a suffix and not for a prefix.
Fixed, I swapped the two cases.
By the way, the reason of WA in your code is
while high-low>1:(because you can havelow != highat the end of the binary search). You can notice that, if you replace that line withwhile high-low>0:, you get TLE. This is because the code can get stuck in an infinite loop in cases likelow = 2,high = 3,mid = 2,low = mid = 2.Hence, you have to put
mid = (low + high + 1) / 2instead ofmid = (low + high) / 2.Also, If you use
while(low<=high)Then to avoid infinite loop use,
Auto comment: topic has been updated by arnav2004 (previous revision, new revision, compare).