https://www.acmicpc.net/problem/1920

매우중요1 : 이진탐색 시 n이 아니라 n-1을 넣어줘야한다!(인덱스 0부터라서)

매우중요2 : 이진탐색 while문 조건은 < 가 아니라 <= 를 해줘야한다!

---

기본 풀이법

def bin_search(start, end, arr, target):
    while start <= end:
        pivot = (start+end)//2     # (중요) while문 안에서 계산!
        
        if target == arr[pivot]:
            return 1
        elif target < arr[pivot]:
            end = pivot-1
        elif target > arr[pivot]:
            start = pivot+1
    return 0
    
n = int(input())
arr = list(map(int,input().split()))
m = int(input())
target_list = list(map(int,input().split()))

arr.sort() # (매우중요)

for target in target_list:
    print(bin_search(0, n-1, arr, target))  # (매우중요) n-1을 넣어주어야 한다

---

set 자료형 활용 -> 시간복잡도와 코드길이 단축

• A를 정렬하지 않고 set으로 만들어 탐색하는 방법이라고 한다. + in 연산자 활용
• 속도는 방법 1 보다는 더 빠르다고 한다!!!!!!!!
• 단, set은 자동 정렬 되지만, 중복 제거되기 때문에 이렇게 존재 유무 파악하는 문제에서만 사용!
  - 개수 세는 문제에선 쓰면 안됨

n = int(input())
arr = set(map(int,input().split()))
m = int(input())
target_list = list(map(int,input().split()))

for target in target_list:
    print(1) if target in arr else print(0)