import sys
input=sys.stdin.readline
def binary_search(start,end,L1,j):
while start <= end:
mid = (start + end) // 2
if L1[mid] == L2[j]: #이분탐색 종료 조건
return 1 #탐색에 성공하면 1 반환
elif L1[mid] > L2[j]:
end = mid - 1
else:
start = mid + 1
return 0 #탐색에 실패하면 0 반환
T=int(input())
for i in range(T):
N=int(input())
L1=list(map(int,input().split())) #수첩1 리스트
L1.sort() #리스트 정렬
M=int(input())
L2=list(map(int,input().split())) #수첩2 리스트
for j in range(M):
print(binary_search(0,N-1,L1,j)) #이분탐색 함수 호출
📌 이분탐색의 시작점과 끝점을 어떻게 잡을 것인가?
이분탐색에서 가장 먼저 생각해야할 부분은 바로 시작점과 끝점 이라고 생각한다.
처음 주어진 리스트는 숫자의 목록만 있을뿐 숫자의 범위는 주어지지 않기 때문에 L1 리스트 자체를 숫자의 범위라고 생각했다.
최소값을 0이아니라 L1[0]의 값을 , 최대값을 임의의 큰 수가 아니라 L1[-1]로 설정하였다.
즉 start=0 , end=N-1 의 값을 가지고 시작하고 L1 의 리스트의 인덱스 0 부터 N-1 까지 탐색한다.
이러면 굳이 최솟값 최대값을 정수 범위로 크게 잡을 필요도없이 범위를 최소화 할 수 있다.
이분탐색에서의 중요한 조건은 탐색할려는 리스트는 정렬되어있어야 한다는 점이다.
L1.sort() 를 꼭 해주자.
L1 리스트를 정렬해주고 이분탐색 함수 binary_search 를 만들어 주었다.
L1[mid] 값이 L2[j] 값보다 크면 end값을 바꿔주고 작으면 start 값을 바꿔준다.
이떄 L2[j] 는 문제의 수첩2의 정수값을 의미한다.
따라서 문제에서 크게 생각할 내용은 다음과 같다.
- 이분탐색의 범위는? -> 수첩 1을 정렬후 인덱스 0값과 N-1값을 최솟값 최대값으로 설정
- 이분탐색의 종료조건은? -> 수첩1의 인덱스 mid값이 수첩2의 값과 같을때
