1920번 수 찾기

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

아이디어

이진 탐색의 개념 그대로 풀면 되는 문제이다.
A는 반드시 정렬되어있어야 이진탐색을 적용할 수 있다.

1. low와 high를 각각 0, A의 마지막 인덱스로 선언
2. 중간 인덱스인 mid를 찾아서 x와 비교
3. 중간 지점이 찾으려는 x보다 크면 high = mid - 1
   중간 지점이 찾으려는 x보다 작으면 low = mid + 1

코드

n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

A.sort()

for x in B:
    low = 0
    high = len(A)-1 # 마지막 인덱스
    flag = False

    while low <= high:
        mid = (low+high) // 2
        if A[mid] == x:
            print(1)
            flag = True
            break
        elif A[mid] > x:
            high = mid - 1
        else: low = mid + 1

    if not flag: # 찾지 못했다면
        print(0)