1920번: 수 찾기 [백준 - Python]

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

1920번: 수 찾기

검사하고 싶은 숫자가 찾고자 하는 문자열에 있는지 없는지를 검사하는 문제이다.

문자열을 인덱스 0번부터 끝까지 뒤지면서 찾아볼 수 있지만 그렇게 되면 시간이 너무 오래걸리게 된다.

따라서 미리 정렬한 뒤, 이분탐색을 통해 원하는 수가 있는지 찾아보게 되면 시간단축을 할 수 있게된다.

이분탐색을 구현을 위하여 끝과 끝, 중간값 3개의 값이 필요하다.

head, tail, middle 3개의 값을 먼저 준비한다.

$$middle = tail + (head - tail)/2$$

• 만약 검사하고싶은 숫자가 middle과 같은 값이면 1을 출력하고 종료
• middle보다 크다면 tail = middle + 1, middle값은 위 수식을 이용해 초기화
• middle보다 작다면 head = middle - 1, middle값은 위 수식을 이용해 초기화
• tail이 head보다 크거나 같다면 0을 출력하고 종료

이 4가지 동작을 무한루프 안에 구현한다면 이분탐색을 쉽게 구현할 수 있다.

N = int(input())
arrayN = list(map(int,input().split()))
M = int(input())
arrayM = list(map(int,input().split()))
arrayN.sort()

def 이분탐색(num):
    head = N-1
    tail = 0

    while(True):
        middle = int(tail + (head-tail)/2)
        if arrayN[middle] == num:
            return print(1)
        elif tail >= head:
            return print(0)
        elif arrayN[middle] > num:
            head = middle-1
        elif arrayN[middle] < num:
            tail = middle+1
for num in arrayM:
    이분탐색(num)