[맛있는물회] <SWEA알고리즘> 4839번 "이진 탐색"

문제 조건

---

 

Input

---

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50

테스트 케이스 별로 책의 전체 쪽 수 P, A, B가 찾을 쪽 번호 Pa, Pb가 차례로 주어진다. 1<= P, Pa, Pb <=1000

 

Output

---

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, A, B, 0 중 하나를 출력한다.

 

생각한 아이디어

---

자료구조를 배운 사람이라면 이진탐색은 아주 간단하게 풀 수 있는 문제이다.

Search 부분에서 가장 먼저 배우며 가장 간단한 방법이다. 

이진탐색은 찾고자 하는 Value 의 값을 Start, Mid, End 와 비교하며 반틈씩 잘라가며 찾는 방식이다. 찾을 때 마다 탐색 범위가 1/2 가 되므로 시간 복잡도는 T(n) = θ(log n)이다.

 

소스코드

T = int(input())
for TC in range(1, T+1):
    P, A, B = map(int, input().split())
    cntA = 0
    cntB = 0
    l = 1
    r = P
    while 1:
        c = int((l+r)/2)
        cntA += 1
        if c == A:
            break
        elif c <= A:
            l = c
        else:
            r = c
    l = 1
    r = P
    while 1:
        c = int((l+r)/2)
        cntB += 1
        if c == B:
            break
        elif c <= B:
            l = c
        else:
            r = c

    if cntA == cntB:
        print("#%d %d" %(TC, 0))
    elif cntA > cntB:
        print("#%d %c" %(TC, 'B'))
    else:
        print("#%d %c" %(TC, 'A'))

 

*파이썬 문법 정리