[SWEA-4839] Binary_Search

링크 : SWEA-4839
이진탐색을 이용해 A, B 두 사람 중 먼저 입력된 지정 페이지를 먼저 펼치는 사람이 이기는 게임이다.

즉, 이진탐색 알고리즘으로 숫자를 쪼갤때(책을 펼칠 때) 숫자을 카운트해 A와 B를 비교해 준다.

🧑‍💻PASS 코드

def binarySearch(page, key):
    start = 1
    end = page
    count = 0

    while start <= end:
        middle = int((start+end)/2)
        count += 1
        if middle == key:
            return count
        elif key < middle:
            end = middle
        elif key > middle:
            start = middle

T = int(input())

for test_case in range(1, T+1):
    P, Pa, Pb = map(int, input().split())   # P 전체 쪽 수, Pa A가 찾을 쪽 수, Pb B가 찾을 쪽 수

    A = binarySearch(P, Pa)
    B = binarySearch(P, Pb)
    
    if A<B:
        result = 'A'
    elif A>B:
        result = 'B'
    else:
        result = 0
        
    print("#%d %s" %(test_case, result))

밑에는 처음 작성한 코드의 일 부분이다. 테스트케이스를 모두 통과 하지못헀다. 조건문 key < middle 일 때와 key > middle 일 때 각각 +1 ,-1을 추가했기 떄문에 일부 테스트케이스에서 실패했다.

while start <= end:
    middle = int((start+end)/2)
    count += 1
    if middle == key:
        return count
    elif key < middle:
        end = middle-1
    elif key > middle:
        start = middle+1

위에 코드로 테스트케이스 10 3 2을 입력하면 A가 출력되어야 하지만 B가 정답으로 출력된다.
A가 2번 B가 3번 만에 찾아야 하는데 middle값을 포함 하지않아 A가 3번 B가 2번만에 찾기 때문이다.

이진탐색 값은 정상적으로 찾아지지만 횟수를 카운트하기 때문에 middle 값을 포함하는지에 따라 카운트되는 횟수가 달라진다.