[SWEA] 4839 이진탐색

문제의 저작권은 SW Expert Academy에 있습니다.
SWEA 4839 이진탐색

코드가 맞는데 왜때문에 도데체 왜!!!!! 계속 에러가 나는지 이해가 안됐다.
아니 6번이나 테스트케이스에서 10개중 8개 맞았다는거다.
알고보니 이 쉬운문제가 계속 오답 나온 이유는 바로 +1 과 -1 때문이다!!!!!!!!!!

아래는 내 pass 코드.

import sys
sys.stdin = open("sample_input.txt")


def binary_search(page, target):
    left = 1
    right = page
    count = 0
    while left <= right:
        mid = int((left + right) / 2)
        if mid == target:
            return count
        elif mid < target:
            left = mid
            count += 1
        elif mid > target:
            right = mid
            count += 1


T = int(input())
for tc in range(1, T + 1):
    page, A, B = map(int, input().split())

    countA = binary_search(page, A)
    countB = binary_search(page, B)
    
    if countA > countB:
        result = 'B'
    elif countA < countB:
        result = 'A'
    else:
        result = 0
    print("#{} {}".format(tc, result))

아래는 계속 에러난 코드. 여기서 인덱스문제인가? 하면서 page를 list로 바꿔서 1부터 400쪽이 포함된 어레이로 하고 이진탐색을 리스트의 인덱스값으로 해봤지만 되지 않음. 왜냐. 이진탐색 while문 안에 left, right를 갱신시켜줄 때 각각 +1, -1를 해주는 것 때문이었다. 악!

사실 이진탐색 자체를 할 때는 어쨌든 찾아지기 때문에 상관은 없지만 지금은 몇번에 나누어 구하는지가 문제였고, 1차이로 검색이 한 번 더 밀릴 수 있기 때문에 틀린 것이었다.

엣지케이스는 10 3 2 이므로 이 걸로 테스트해보시길 ... 그러면 저렇게 -1, +1 하는것과 안하는게 결과값의 차이가 난다.

T = int(input())


def binary_search(page, target):
    left = 1
    right = page
    count = 1
    while left <= right:
        mid = int((left + right) / 2)
        if mid == target:
            return count
        elif mid < target:
            left = mid + 1
            count += 1
        elif mid > target:
            right = mid - 1
            count += 1



for tc in range(1, T + 1):
    page, A, B = map(int, input().split())

    countA = binary_search(page, A)
    countB = binary_search(page, B)
    if countA > countB:
        result = 'B'
    elif countA < countB:
        result = 'A'
    else:
        result = 0
    print("#{} {}".format(tc, result))