Блог пользователя Carbon

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

Автор Carbon, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить