수찾기

문제이해
 M_list의 수가 N_list에 있으면 1 아니면 0 출력

매우간단한문제지만

N = int(input())
lst = list(map(int,input().split()))
M = int(input())
lst2 = list(map(int,input().split()))
for i in lst2:
    if i in lst:
        print(1)
    else:
        print(0)

직관적으로 푸니 시간초과뜸..

 

이진탐색

 1. 정렬한후 배열의 중간값과 우리가 찾아야하는 값을 비교해서 찾기

 

N = int(input())
lst = list(map(int,input().split()))
M = int(input())
lst2 = list(map(int,input().split()))

lst.sort()

for i in lst2:
    start = 0 # 시작 인덱스
    end = N-1 # 마지막 인덱스
    found = 0
    while start<=end:
        mid = (start+end) // 2
        if lst[mid] == i:
            found = 1
            break
        elif lst[mid] > i:
            end = mid-1
        else :
            start = mid+1
    print(found)