이진 검색(이분 탐색)

이진 검색

• 정렬된 배열에 한해서 사용 가능한 검색 알고리즘

• 매 반복시마다 배열의 가운데 원소와 key값과의 비교를 통해 범위를 절반씩 줄여나간다.

• 시간복잡도가 O(n)인 선형 검색보다 좋다. O(logn)

직접 구현해본 이진 검색 on 백준 1920

import sys

N = int(sys.stdin.readline())
Ns = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
Ms = list(map(int, sys.stdin.readline().split()))


Ns.sort()
result = []
for num in Ms:
    start = 0
    end = len(Ns) - 1
    while True:
        if start > end:
            result.append(0)
            break
        middle = (start + end)//2
        if num == Ns[middle]:
            result.append(1)
            break
        elif num < Ns[middle]:
            end = middle - 1
        elif num > Ns[middle]:
            start = middle + 1

print(result)
>> input 
5
4 1 5 2 3
5
1 3 7 9 5
>> output
[1, 1, 0, 0, 1]