[알고리즘] 이분 탐색(binary search)

이진 탐색, 이분 탐색(binary search)이란?

 

말 그대로 이등분 해가며 탐색하는 알고리즘이다.

 

찾아야할 숫자가 100이라면

1부터 100까지 하나씩 찾아가는 선형 탐색에 비해

 

이분 탐색을 활용해

이등분씩 해나가며 탐색을 하면 시간복잡도를 훨씬 줄일 수 있다.

 

 

이분 탐색 기본 코드 예제

def binary_search(array: list, target: int):
    left = 0
    right = len(array) - 1

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

 

array의 길이를 기준으로 왼쪽과 오른쪽을 나누고 array의 중간 값과 target 값을 비교해

크다면 오른쪽으로 작다면 왼쪽으로 다시 이등분 해주는 식이다.

 

# 심화
def recursive_binary_search(array, left, right, target):
    if left > right:
        return 0
    mid = (left + right) // 2
    if array[mid] > target:
        right = mid - 1
    elif array[mid] < target:
        left = mid + 1
    else:
        return 1
    return recursive_binary_search(array, left, right, target)

 

 

 

활용 예제 코드

input()
n = sorted(list(map(int, input().split())))
M = int(input())
m = list(map(int, input().split()))

def zero_or_one(n, i):
    left = 0
    right = len(n) - 1
    
    while left <= right:
        mid = (left + right) // 2

        if i > n[mid]:
            left = mid + 1

        elif i < n[mid]:
            right = mid - 1

        else:
            return 1
    return 0

for i in m:
    print(zero_or_one(n, i))