이분 탐색(Binary Search)

(이미지 출처 : https://blog.weirdx.io/post/3121)

선형 탐색에 비해

이분 탐색이 선형 탐색에 비해 빠르게 검색할 수 있는 장점이 있다.

이분 탐색은 오름차순 혹은 내림차순으로 정렬된 배열 구조에서 효율적이다.

백준 1920번 - 수 찾기

import sys
# sys.stdin = open('input.txt')
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a.sort()

m = int(input())
b = list(map(int, input().split()))

def check(x):
    lt = 0
    rt = n - 1

    while lt <= rt:
        mid = (lt + rt) // 2

        if a[mid] == x:
            return 1

        elif a[mid] > x:
            rt = mid - 1

        else:
            lt = mid + 1

    return 0

for i in b:
    print(check(i))

결정 알고리즘

이분 탐색은 결정 알고리즘이라는 방법론에서 사용한다. 우리가 찾고자 하는 답이 특정한 범위 내에 있다는 것을 미리 알 수 있을 때, 그 답이 답으로서 유효한지 유효하지 않은지 확인을 하고 답이 될만하다, 싶으면 범위를 절반으로 줄이는(여기서 이분 탐색이 사용된다) 방법이다. 더 좋은 값이 있는지 계속해서 찾아가는 것이다.

• 미리 범위를 가늠할 수 있어야 하고, 이분 탐색을 쓰기 위해 정렬되어 있어야 한다.

백준 2805번 - 나무 자르기

import sys
# sys.stdin = open('input.txt')
input = sys.stdin.readline

n, m = map(int, input().split())
line = list(map(int, input().split()))
longest = max(line)

def count(len):
    rest = 0

    for i in line:
        if len >= i:
            continue
        else:
            rest += i - len

    return rest

lt = 1
rt = longest
res = 0
while lt <= rt:
    mid = (lt+rt) // 2

    if count(mid) >= m:
        lt = mid + 1
        res = mid

    else:
        rt = mid - 1

print(res)

m이 0이라면, 잘라볼 수 있는 최대 길이는 20이다. 따라서 여기서는 최대 범위(rt)가 20(longest)가 된다. 이렇게 잘라보려는 나무의 길이들은 최소 1 이상이므로 최소 범위(lt)는 1이다. 위 코드와 같이 이분 탐색을 이용하지만 맨 위 코드는 check 함수 내에서 while문을 돌다가 원하는 값을 찾을 시 종료되는 반면, 해당 코드는 최적의 값을 찾아나가는 과정이라 log N만큼 다 돌게 된다.