Carbon's blog

Wrong answer in Codeforces Round #678 (Div. 2)

By Carbon, history, 4 years ago, In English

Hello, can someone explain me in this question BINARY SEARCH for the test case 3 1 2 my answer is giving answer 2 but the judge says it should be 0. Can someone explain me this test case. thanks in advance. 96599228

  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Their binary search is a bit different in the sense that they keep going even after finding x.
Here if we consider 1 3 2 and 2 1 3. Apply BS implementation.
So for 1 3 2 left = 0, right = 3 gives mid = 1, since a[1] = 3(it's fixed) so left = 1(mid) + 1 = 2.
Now we have left = 2, right = 3.
Again calculating mid, mid = 2, Now no matter what you place 1 or 2 in position = 2, you will always satisfy a[mid] <= x, so left = 2(mid) + 1 i.e, left = 3, right = 3 and now BS will terminate.
So you see now if you do a[left-1] == x, it's not true. So the answer will be 0.

→ Reply