176. 1920(수 찾기) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())
A = sorted(list(map(int, input().split())))
M = int(input())
B = list(map(int, input().split()))


def binarySearch(array, target):
    start = 0
    end = len(array) - 1
    mid = (end+start)//2

    while(end - start >= 0):
        if(array[mid] == target):
            return 1
        elif(array[mid] <= target):
            start = mid + 1
        else:
            end = mid - 1
        mid = (end + start) // 2
    return 0


for i in B:
    print(binarySearch(A, i))

문제요약

B의 숫자가 A안에 있는지 찾아보아라

설명

반복문을 사용해서 문제를 푼다면 시간초과가 발생할 수 있다.

때문에 이분탐색 기법을 사용해야 한다.

 

이분 탐색 기법은 간단히 말해 정렬된 배열에서 데이터를 찾으려는 시도할 때 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법이다.

 

자세한 알고리즘 설명은 아래 링크에 설명되어 있다.

https://smhope.tistory.com/469?category=1056187 

[알고리즘 | 자료구조] 이분 탐색(Binary Search)