SWEA 4839. 이진탐색 알고리즘 - 파이썬

SWEA 문제 4839. 이진탐색

 

문제의 저작권은 SW Expert Academy에 있습니다.

 

 

 

🎈 이진탐색은 범위의 중간값과 비교하며 범위를 줄여나가는 탐색으로 for문을 돌면서 하나씩 찾는 것보다 훨씬 빠릅니다! 시간복잡도는 log N입니다. 다만, 이진탐색은 정렬이 되어 있어야 가능하단 것!!

 

정렬되지 않은 경우에는 정렬하는 시간+ 이진탐색 시간 이렇게 함께 생각해줘야 합니다!

 

 

 

# 이진탐색 구현 함수
def binary_search(page, P):
    start = 1
    end = page
    middle = 0
    count = 1
    while P != middle:
        middle = int((start + end) / 2)
        if middle > P:
            end = middle
        else:
            start = middle
        count += 1
    return count

T = int(input())
for tc in range(1, T+1):
    pages, Pa, Pb = map(int, input().split())
    A = binary_search(pages, Pa)
    B = binary_search(pages, Pb)
    ans = 0
    if A < B:
        ans = 'A'
    elif A > B:
        ans = 'B'
    else:
        ans = 0
    print(f'#{tc} {ans}')