[백준][Python][1920][이분탐색] 수 찾기

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

1920번: 수 찾기

이분 탐색 문제다.

 

이분 탐색 알고리즘을 구현하는 문제다.

 

1. 행렬을 정렬한다.
2. left, right를 각각 0, 길이-1로 한다.
3. left <= right 인 동안 loop을 돌면서
   1. mid = (left+right ) /2를 한다.
   2. arr[mid]가 찾는 값보다 크면right = mid-1
   3. arr[mid]가 찾는 값보다 작으면 left = mid+1
   4. 찾는 값이면 위치 반환
4. 반환을 못하면 l>r인 상황이 되어 loop탈출 -> -1 실패 반환

 

import sys

n = int(sys.stdin.readline())

a = [int(i) for i in sys.stdin.readline().split()]

m = int(sys.stdin.readline())

b = [int(i) for i in sys.stdin.readline().split()]


def binsearch(arr, x):

    l, r = 0, len(arr)-1

    while l <= r:
        mid = (l+r)//2
        if arr[mid] > x:
            r = mid-1

        elif arr[mid] < x:
            l = mid+1

        else:
            return mid

    return -1


a.sort()

for c in b:
    tmp = binsearch(a, c)

    if tmp != -1:
        print(1)

    else:
        print(0)