1. 문제

---

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

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

2. 아이디어

---

• 이진 탐색

  1. 탐색할 숫자를 입력받고 이진 탐색을 위해 sort()로 정렬한다.
  2. 두 번째 입력 리스트를 받고 요소 하나씩 1에서 정렬한 리스트에서 이진탐색을 한다.
  3. 값이 있으면 1, 없으면 0을 반환하고 출력한다.

이진 탐색 방법

1. 중간 인덱스 찾기
2. 중간 값보다 찾고자 하는 값이 작으면 왼쪽, 크면 오른쪽 확인
3. while문에 의해 반복

출처 : https://j-ungry.tistory.com/205

3. 코드

---

mine

import sys

def binarySearch(array,target,start,end): 
  while start <= end : 
    mid = (start+end) // 2 #중간점 찾기 
  #찾은 경우 중간점 인덱스 반환 
    if array[mid] == target : 
      return 1 
  #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 
    elif array[mid] > target: 
      end = mid -1 
  #중간점의 값보다 찾고자 하는 값이 큰 경우 왼쪽 확인 
    else: 
      start = mid + 1
  return 0

input = lambda: sys.stdin.readline()
n = int(input())
n_arr = list(map(int, input().split()))
n_arr.sort()
m = int(input())
m_arr = list(map(int, input().split()))

for arr in m_arr:
  print(binarySearch(n_arr, arr, 0 , n-1))