1920 수찾기

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

python으로 푸는데 in 을 사용해서 값이 존재하는지 판단하여 풀 수 있을 것이라 생각했으나

 

python의 in은 O(N) 연산이라고 한다.

 

O(N) 연산이기 때문에 100000**2  이고

 

이진 탐색을 쓰면 정렬에 O(NlogN), 찾는데 O(logN)이므로 훨씬 빠르게 찾을 수 있다.

 

앞으로는 되도록 이진탐색을 이용하는 습관을 들이는것이 바람직한것 같다.

 

 

'''
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
'''
import sys
n = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split(" ")))
m = int(sys.stdin.readline().rstrip())
B = list(map(int, sys.stdin.readline().rstrip().split(" ")))

def binary_search(target, start, end):
  global A
  
  while(start<=end):
    mid = (start+end)//2
    if(A[mid] == target):
      return True
    else:
      if( A[mid] > target ):
        end = mid-1
      else:
        start = mid+1
  
  return False
  
A = sorted(A)
for n in B:
  if(binary_search(n, 0, len(A)-1)):
    print(1)
  else:
    print(0)