백준 - 1920번 수 찾기(이분탐색)

이분탐색 기본 문제 풀어보기
문제
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안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.

출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

접근 방식
입력으로 최대 10만 개의 정수와 정수가 존재하는지 검사할 최대 10만 개의 M 이 주어지므로, 간단히 생각해서 시간 복잡도가 O(N)인 count()함수를 N 번쓴다면 O(N^2) = 10,000,000,000 으로 최대 100억번의 연산이 필요하다.
1초에 2천만번(20,000,000)의 연산이 가능한 파이썬으로는
O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 1초 안에 수행이 가능하다. (log 100,000 = 약 16, 2^16=65,536)

즉, N개의 정수를 일단 정렬 한 뒤 ~ O(NlogN)
정렬된 리스트에서 이분 탐색을 통해 존재 여부를 탐색하면 ~ O(MlogN)
총 시간복잡도는 NlogN + MlogN 이므로 O(NlogN)이 되서 문제 풀이가 가능할 것이다.

아래의 풀이와 같이 이분탐색을 구현하여 풀 수 있다.

N,a=int(input()), list(map(int,input().split()))
a.sort()
def binary_search(arr,a,s,e):
    while s <= e:
        mid = (s+e) //2
        if arr[mid] == a:
            return 1
        elif arr[mid] > a:
            e = mid-1
        elif arr[mid] < a:
            s = mid+1
    return 0

M = int(input())    
for i in map(int,input().split()):
    print(binary_search(a,i,0,N-1))

숏코딩 분석하기
문제 취지였던 이분탐색이 아닌 key, value의 dictionary 자료 형으로 만들어서 딕셔너리 안에 key 값이 존재하는지를 반환하였다.

z,z,t,t=open(0)
z={*z.split()} # dictionary구조로 만들기
# z의 키 값을 찾아 있으면 True로 반환 된 것을 
# implicit Type Conversion을 통해서 0과 1로 바꿔줌
for i in t.split():print(+(i in z))