[SWEA] # 5207 이진탐색(binary search)(python)

 
이진 탐색시 왼쪽 오른쪽 번갈아가면서 탐색을 했을 때에만 count 하는 문제이다. 
 
먼저, 이진탐색 기본 코드는 다음과 같다. 

def binary_search(low, high, target):
    # 기저조건
    # target 을 발견하지 못하면 종료
    if low > high:
        return -1

    mid = (low + high) // 2

    # 발견했다면
    if target == arr[mid]:
        return mid

    # target 이 mid 보다 작다 == target 이 mid 의 왼쪽에 존재한다 == high 를 mid - 1로
    elif target < arr[mid]:
        return binary_search(low, mid - 1, target)
    else:
        return binary_search(mid + 1, high, target)

 
소주뚜껑 번호 맞추는 게임할 때, up down으로 반으로 범위를 좁혀 가면서 번호를 맞추는 것처럼
설정한 범위의 가운데를 기준으로 target이 오른쪽에 있는지, 왼쪽에 있는지를 확인하면서 타겟을 찾는 원리이다.
 
따라서 이진탐색을 위해서는 배열이 정렬(sort)되어 있어야 한다.
배열을 정렬하는 방법에는 counting sort, bubble sort, quick sort, merge sort 등 다양한 방법이 있는데
일단은 가장 간단한 방법인 sort 함수를 사용해서 문제를 해결했다 ㅎㅎ.. 
 

def bin_search(low, high, arr, target):    # 시작점, 끝점, 기본 배열, 타겟값
    check = 0
    while low <= high:
        mid = (low+high)//2

        if arr[mid] < target:     # 타겟이 오른쪽
            if check == 1:         # 다시 오른쪽으로 왔으면 넘기기
                return False
            low = mid + 1           # 타겟이 오른쪽에 있으면 최솟값을 mid+1로
            check = 1               # 오른쪽 검사 표시

        elif arr[mid] > target:       # 타겟이 왼쪽에
            if check == -1:             # 다시 왼쪽으로 왔으면 넘기기
                return False
            high = mid -1
            check = -1              # 왼쪽 검사 표시

        else:                   # 중앙값이랑 타겟이랑 같으면
            return True         # True

    return False


T = int(input())
for tc in range(1, T+1):
    ans = 0
    N, M = map(int, input().split())
    A = sorted(map(int, input().split()))
    B = list(map(int, input().split()))
    for i in range(len(B)):
        if bin_search(0, N-1, A, B[i]):
            ans += 1
    print(f'#{tc} {ans}')

 
오른쪽 확인 표시를 1로, 왼쪽 확인 표시를 -1로 해서 왼쪽, 오른쪽 번갈아가면서 체크 하는지를 확인해줬다.