이진 탐색: 정렬된 리스트에서 특정한 값을 찾아내는 알고리즘

1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.
2. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,
3. X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
4. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

def BinarySearch(arr, val, low, high):
    if low > high:
        return False #해당 배열에 타겟 숫자 미존재
    
    mid = (low + high) // 2 #위치 기반으로 찾는 것
    
    if arr[mid] > val:
        return BinarySearch(arr, val, low, mid - 1) #수가 중앙 값보다 아래 있는 경우
    elif arr[mid] < val:
        return BinarySearch(arr, val, mid + 1, high) #수가 중앙 값보다 위에 있는 경우
    else:
        return True #아니면 숫자를 출력 -> return val

10815: 숫자카드

10815번: 숫자 카드

map, split

[파이썬 / Python] map(int, input().split())에 대해

#10815

n = int(input()) #숫자카드 개수
card = list(map(int, input().split()))
card.sort()

def binary_search(choose):
    l = 0
    r = n-1
    while l <= r:
        mid = (l+r)//2
        if card[mid] == choose:
            return 1 #가지고 있는 경우
        elif card[mid] > choose:
            r = mid - 1
        else:
            l = mid + 1
    return 0 #가지고 있지 않을 모든 경우
        

m = int(input()) #선택할 카드 개수
for choose in list(map(int, input().split())): #공백으로 구분 입력
    print(binary_search(choose), end = ' ')