[SWEA 4839][파이썬 S/W 문제해결 기본]. 2일차 - 이진탐색

문제

코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다.
짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다.
예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다.
찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다.
A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다.

 

내 코드

def binarySearch(start, end, key, cnt):
    middle = (start+end)//2
    if middle == key:
        return cnt
    if key > middle:
        return binarySearch(middle, end, key, cnt+1)
    else:
        return binarySearch(start, middle, key, cnt+1)
T = int(input())
for test_case in range(1, T + 1):
    P, A, B =map(int,input().split())
    cntA = binarySearch(1, P, A, 0)
    cntB=binarySearch(1, P, B, 0)
    if cntA > cntB:
        print("#{} {}".format(test_case, 'B'))
    elif cntA == cntB:
        print("#{} {}".format(test_case, '0'))
    else:
        print("#{} {}".format(test_case,'A'))

 

이진탐색 내가 어려워 하는 알고리즘 중 하나이다. 문제를 더 풀어봐야 자신감이 생길듯하다 !

그리고 이런 라이브러리도 있음 !

 

* bisect 라이브러리 
   : 이진탐색과 관련된 함수들을 제공  (정렬되어 있어야 함)

import bisect
arr = [1, 3, 5, 7, 9]

# bisect_left 함수
print(bisect.bisect_left(arr, 4))  # 2

# bisect_right 함수
print(bisect.bisect_right(arr, 4))  # 2

# bisect 함수 
print(bisect.bisect(arr, 4))  # 2

# insort_left 함수 
bisect.insort_left(arr, 4)
print(seq)  # [1, 3, 4, 5, 7, 9]

# insort_right 함수 
bisect.insort_right(arr, 4)
print(seq)  # [1, 3, 4, 4, 5, 7, 9]