1. 문제

---

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

출처 : https://www.acmicpc.net/problem/10815

2. 아이디어

---

• mine

  1. 이분 탐색을 한다.
  2. 찾으면 1을 출력 후 return 아니면 0을 출력

이분탐색 출처 : https://wayhome25.github.io/cs/2017/04/15/cs-16/

3. 코드

---

mine

import sys
input = sys.stdin.readline

def binary_search(a, x):
  start = 0
  end = len(a)-1

  while start <= end:
    mid = (start+end) // 2
    if x == a[mid]: # 발견 
      print(1, end = ' ')
      return
    elif x > a[mid]: # 찾는 값이 크면 오른쪽으로 범위를 좁혀 계속 탐색
      start = mid + 1
    else: # 찾는 값이 작으면 왼쪽으로 범위를 좁혀 계속 탐색
      end = mid - 1
  print(0, end = ' ') # 미발견

n1 = int(input())
arr1 = list(map(int, input().split()))
n2 = int(input())
arr2 = list(map(int, input().split()))
arr1.sort() # 탐색할 리스트 정렬
for i in arr2:
  binary_search(arr1, i)