[python] SWEA : 이진 탐색

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

[key point]

- 이진탐색이므로 탐색할 배열 정렬하기

- 양쪽을 번갈아가며 탐색하는지 검사하기 

 

[구현]

def binarySearch(arr, start, end, target):
    # 번갈아 방문하는지 검사
    check = 0
    while start <= end:
        mid = (start + end)//2
        if arr[mid] < target:
            # 오른쪽을 반복 방문했다면
            if check == 1:
                return False
            start = mid + 1
            check = 1
        elif arr[mid] > target:
            # 왼쪽을 반복 방문했다면
            if check == -1:
                return False
            end = mid - 1
            check = -1
        else:
            return True
    return False


for tc in range(1, int(input())+1):
    result = 0
    n, m = map(int, input().split())
    # 이진탐색이므로 탐색할 배열 정렬 
    a_lst = sorted(map(int, input().split()))
    for b in list(map(int, input().split())):
        if binarySearch(a_lst, 0, n-1, b):
            result += 1
    print(f'#{tc} {result}')