def binarySearch(ele, start, end):
global A
if start > end:
return 0
mid = (start + end) // 2
if A[mid] == ele:
return 1
elif A[mid] > ele:
return binarySearch(ele, start, mid - 1)
else:
return binarySearch(ele, mid + 1, end)
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
A.sort() #이진 탐색을 하기 위해서 미리 정렬을 수행한다.
for ele in B:
result = binarySearch(ele, 0, N - 1)
print(result)
문제 조건을 보면 데이터의 개수가 100,000 인것을 알 수 있다
이코테에서 말한대로 NlogN시간 내에 해결해야 하는 것을 알 수 있다.
데이터의 개수가 N 이므로 탐색시간은 logN으로 끝내야 한다
고로 이분탐색을 써야한다고 판단 하였다.
우선 이분탐색은 정렬된 상태로 시작해야 하므로 NlogN으로 정렬을 알 수 있는 자체 라이브러리 메소드를 사용하였고 이분탐색을 재귀로 구현해서 해결하였다.
재귀 이분탐색은 익숙해서 그런지 쉽게 작성했는데
이코테에서 반복문이 좋다고 했었다. 재귀로 작성하면 함수에 의한 메모리 소모가 크다고 했었다.
다음엔 반복문으로 풀어보겠다