이진 탐색과 빠르게 찾는 방법

왜 빠르게 찾는 방법이 필요한가

배열에서 원하는 값을 찾는 가장 단순한 방법은 앞에서부터 하나씩 확인하는 것입니다. 예를 들어 숫자 카드가 100장 있으면 최대 100장을 확인해야 합니다. 카드가 100만 장이라면 최대 100만 번 확인해야 합니다. 이 방법은 정확하지만, 입력이 커질수록 느려집니다.

이때 데이터가 정렬되어 있다면 훨씬 빠르게 찾을 수 있습니다. 정렬된 데이터에는 중요한 규칙이 있습니다.

가운데 값을 확인하면, 찾는 값이 왼쪽에 있는지 오른쪽에 있는지 판단할 수 있다.

이 규칙을 이용해 탐색 범위를 매번 절반으로 줄이는 방법이 이진 탐색입니다. 이진 탐색은 한 번 확인할 때마다 남은 후보의 절반을 버립니다. 그래서 시간 복잡도는 O(log n)입니다. 정렬이 단순히 보기 좋게 데이터를 정리하는 작업이었다면, 이 장에서는 정렬된 데이터가 어떻게 빠른 탐색으로 이어지는지 배웁니다.

AI 생성 이미지

이진 탐색이 정렬된 데이터에서만 작동하는 이유

다음 숫자 카드가 오름차순으로 정렬되어 있다고 해 봅시다.

[2, 5, 8, 12, 16, 23, 38]

여기서 16을 찾고 싶습니다. 처음부터 하나씩 보면 2, 5, 8, 12, 16 순서로 확인해야 합니다. 하지만 이진 탐색은 가운데부터 봅니다.

가운데 값은 12입니다.

[2, 5, 8, 12, 16, 23, 38]
          ↑
        가운데

찾는 값 16은 12보다 큽니다. 배열이 정렬되어 있으므로 12의 왼쪽에 있는 값들은 모두 12보다 작거나 같습니다. 따라서 왼쪽에는 16이 있을 수 없습니다.

이제 왼쪽 절반을 버리고 오른쪽만 봅니다.

[16, 23, 38]

다시 가운데를 확인하면 23입니다. 찾는 값 16은 23보다 작습니다. 정렬되어 있으므로 23의 오른쪽 값들은 모두 23보다 크거나 같습니다. 따라서 오른쪽을 버릴 수 있습니다.

남은 값은 16이고, 원하는 값을 찾았습니다.

중요한 점은 이것입니다.

이진 탐색은 값을 비교한 뒤 한쪽 범위를 통째로 버리는 알고리즘이다.

그런데 배열이 정렬되어 있지 않다면 가운데 값이 작다고 해서 왼쪽 전체를 버릴 수 없습니다. 예를 들어 다음 배열을 봅시다.

[16, 2, 38, 5, 12, 23, 8]

가운데 값이 5라고 해서 왼쪽에 16이 없다고 말할 수 없습니다. 실제로 16은 왼쪽에 있습니다. 그래서 이진 탐색은 반드시 정렬된 데이터에서 사용해야 합니다.

정렬되지 않은 데이터에 이진 탐색을 적용하고 싶다면 먼저 정렬해야 합니다. 다만 정렬에는 보통 O(n log n) 시간이 걸립니다. 한 번만 찾을 거라면 그냥 한 번 순회하는 O(n) 탐색이 더 단순할 수 있습니다. 하지만 같은 데이터에서 여러 번 찾는다면, 한 번 정렬해 두고 이진 탐색을 반복하는 방식이 유리할 수 있습니다.

기본 이진 탐색의 생각 순서

이진 탐색에서는 세 변수를 자주 사용합니다.

• left: 아직 답이 있을 수 있는 가장 왼쪽 위치

• right: 아직 답이 있을 수 있는 가장 오른쪽 위치

• mid: 현재 확인할 가운데 위치

아래 설명은 배열의 위치가 0부터 시작한다고 가정합니다. 예를 들어 길이가 7인 배열의 위치는 0부터 6까지입니다.

처음에는 배열 전체가 후보입니다.

left = 0
right = 배열 길이 - 1

그리고 가운데 위치를 계산합니다.

mid = (left + right) // 2

여기서 //는 나눗셈 결과에서 소수 부분을 버리는 정수 나눗셈이라고 생각하면 됩니다.

이제 arr[mid]와 찾는 값 target을 비교합니다.

1. arr[mid] == target이면 찾았습니다.

2. arr[mid] < target이면 찾는 값은 오른쪽에만 있을 수 있습니다. 따라서 left = mid + 1로 바꿉니다.

3. arr[mid] > target이면 찾는 값은 왼쪽에만 있을 수 있습니다. 따라서 right = mid - 1로 바꿉니다.

의사코드는 다음과 같습니다.

function binary_search(arr, target):
    left = 0
    right = length(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return true
        else if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return false

반복 조건이 left <= right인 이유는 후보가 하나 남았을 때도 확인해야 하기 때문입니다. 예를 들어 left와 right가 둘 다 같은 위치를 가리키면 후보가 정확히 하나 남은 상태입니다. 이때 확인하지 않고 끝내면 답을 놓칠 수 있습니다.

이진 탐색의 시간 복잡도는 O(log n)입니다. 배열 크기가 1,024라면 절반씩 줄였을 때 약 10번 정도면 후보가 1개까지 줄어듭니다. 100만 개도 약 20번 정도의 비교로 충분합니다. 이 점이 하나씩 찾는 탐색과 가장 큰 차이입니다.

존재 여부 찾기와 위치 찾기는 다르다

처음 배우는 이진 탐색은 보통 "값이 있는가?"를 찾습니다. 값이 발견되면 바로 true를 반환하면 됩니다. 하지만 실전 문제에서는 "그 값이 처음 나타나는 위치" 또는 "마지막으로 나타나는 위치"를 물을 때가 많습니다.

다음 배열을 봅시다.

[1, 2, 2, 2, 4, 5]

2는 여러 번 등장합니다. 기본 이진 탐색은 이 중 어느 위치의 2를 찾을지 보장하지 않습니다. 가운데에서 찾으면 바로 멈추기 때문입니다.

만약 첫 번째 2의 위치를 찾아야 한다면, 값을 찾았더라도 멈추면 안 됩니다. 찾은 위치를 기록해 두고, 더 왼쪽에도 같은 값이 있는지 계속 확인해야 합니다.

function first_position(arr, target):
    left = 0
    right = length(arr) - 1
    answer = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] < target:
            left = mid + 1
        else:
            if arr[mid] == target:
                answer = mid
            right = mid - 1

    return answer

이 코드에서 arr[mid] == target이면 answer에 저장합니다. 하지만 바로 끝내지 않고 right = mid - 1로 바꿉니다. 더 왼쪽에도 같은 값이 있을 수 있기 때문입니다.

반대로 마지막 위치를 찾으려면 값을 찾은 뒤 오른쪽을 더 확인해야 합니다.

function last_position(arr, target):
    left = 0
    right = length(arr) - 1
    answer = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] > target:
            right = mid - 1
        else:
            if arr[mid] == target:
                answer = mid
            left = mid + 1

    return answer

예를 들어 배열이 [1, 2, 2, 2, 4, 5]이고 target = 2라면 첫 번째 위치는 1, 마지막 위치는 3입니다. 위치를 0부터 세기 때문입니다.

값의 개수를 구하고 싶다면 먼저 첫 번째 위치와 마지막 위치를 각각 구합니다.

first = first_position(arr, target)
last = last_position(arr, target)

if first == -1:
    count = 0
else:
    count = last - first + 1

값이 없으면 first_position이 -1을 반환하므로, 이 경우를 따로 처리해야 합니다.

답을 직접 찾기 어렵다면 '가능한가?'를 묻기

이진 탐색은 배열에서 값을 찾을 때만 쓰는 기법이 아닙니다. 더 중요한 확장 방식이 있습니다. 바로 정답의 범위를 정해 두고, 어떤 값이 가능한지 판정하면서 답을 찾는 방법입니다.

처음에는 조금 낯설 수 있습니다. 하지만 핵심은 단순합니다.

정답을 바로 구하기 어렵다면, 후보 값 하나를 정한 뒤 "이 값으로 가능한가?"를 물어본다.

이 방법이 작동하려면 가능 여부가 한 방향으로 정리되어야 합니다. 예를 들어 어떤 값 이상은 모두 가능하고, 그보다 작은 값은 모두 불가능하다면 이진 탐색을 쓸 수 있습니다. 이렇게 가능과 불가능이 한쪽 방향으로만 바뀌는 성질을 단조성이라고 생각하면 됩니다.

택배 상자 예시로 생각해 봅시다.

상자 무게가 다음과 같습니다.

[3, 2, 2, 4, 1, 4]

상자는 순서대로 실어야 하고, 최대 3일 안에 모두 옮겨야 합니다. 트럭의 최소 적재 용량을 구하려고 합니다.

트럭 용량이 5라면 가능한지 확인해 봅시다.

1일차: 3 + 2 = 5
2일차: 2
3일차: 4 + 1 = 5
4일차: 4

4일이 필요하므로 불가능합니다.

트럭 용량이 6이라면 어떨까요?

1일차: 3 + 2 = 5
2일차: 2 + 4 = 6
3일차: 1 + 4 = 5

3일 안에 가능하므로 용량 6은 가능합니다.

여기서 중요한 규칙이 보입니다.

용량 4: 불가능
용량 5: 불가능
용량 6: 가능
용량 7: 가능
용량 8: 가능

어떤 용량으로 가능하다면, 그보다 큰 용량도 가능합니다. 그래서 우리는 "처음으로 가능한 용량"을 이진 탐색으로 찾을 수 있습니다.

먼저 판정 함수를 만듭니다. 판정 함수는 후보 용량 capacity를 받아서, 그 용량으로 D일 안에 옮길 수 있는지 알려 줍니다.

function can_ship(weights, D, capacity):
    days = 1
    current = 0

    for weight in weights:
        if weight > capacity:
            return false

        if current + weight <= capacity:
            current = current + weight
        else:
            days = days + 1
            current = weight

    return days <= D

이제 가능한 최소 용량을 찾습니다.

function min_capacity(weights, D):
    left = max(weights)
    right = sum(weights)
    answer = right

    while left <= right:
        mid = (left + right) // 2

        if can_ship(weights, D, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

left를 max(weights)로 두는 이유는 가장 무거운 상자 하나는 반드시 실을 수 있어야 하기 때문입니다. right를 sum(weights)로 두는 이유는 모든 상자를 하루에 한 번에 싣는 경우가 가능한 최대 용량이기 때문입니다.

이런 유형을 흔히 답을 이진 탐색한다고 말합니다. 정확히는 정답 후보 범위에서 가능한 값과 불가능한 값의 경계를 찾는 것입니다. 배열의 값 자체를 찾는 것이 아니라, 정답이 될 수 있는 숫자 범위에서 경계를 찾는다고 보면 됩니다.

최솟값을 찾을 때는 보통 다음 흐름입니다.

가능하다면:
    답 후보로 저장하고 더 작은 값을 시도한다
불가능하다면:
    더 큰 값을 시도한다

반대로 최댓값을 찾는 문제도 있습니다. 예를 들어 랜선을 같은 길이로 잘라서 필요한 개수 이상 만들 수 있는 최대 길이를 찾는 문제를 생각할 수 있습니다. 이 경우 어떤 길이로 필요한 개수를 만들 수 있다면, 그보다 짧은 길이로도 보통 만들 수 있습니다. 반대로 길이를 너무 길게 잡으면 필요한 개수만큼 만들지 못합니다.

길이 1: 가능
길이 2: 가능
길이 3: 가능
길이 4: 불가능
길이 5: 불가능

이런 문제에서는 "마지막으로 가능한 값"을 찾아야 합니다.

가능하다면:
    답 후보로 저장하고 더 큰 값을 시도한다
불가능하다면:
    더 작은 값을 시도한다

즉, 답을 이진 탐색할 때는 먼저 가능한 쪽과 불가능한 쪽의 방향을 확인해야 합니다.

자주 틀리는 부분

정렬되지 않은 배열에 이진 탐색을 사용한다

이진 탐색은 정렬된 데이터에서만 한쪽 범위를 안전하게 버릴 수 있습니다. 정렬되어 있지 않은 배열이라면 먼저 정렬해야 합니다. 단, 원래 위치가 필요한 문제라면 정렬하기 전에 원래 인덱스를 함께 저장해야 할 수 있습니다.

mid를 제외하지 않아 무한 반복이 생긴다

기본 이진 탐색에서 arr[mid] < target이면 left = mid + 1로 이동해야 합니다. left = mid라고 쓰면 후보 범위가 줄지 않을 수 있습니다.

예를 들어 left = 3, right = 4일 때 mid = 3입니다. 여기서 다시 left = mid를 하면 left는 계속 3입니다. 그러면 같은 mid를 반복해서 계산하며 끝나지 않을 수 있습니다.

첫 번째 위치와 마지막 위치를 찾는 규칙을 섞는다

값을 찾았을 때 왼쪽을 더 볼지, 오른쪽을 더 볼지에 따라 결과가 달라집니다.

• 첫 번째 위치: 값을 찾은 뒤 right = mid - 1

• 마지막 위치: 값을 찾은 뒤 left = mid + 1

값을 찾았다고 바로 반환하면 중복된 값이 있을 때 원하는 위치를 구하지 못할 수 있습니다.

판정 함수가 한 방향으로 정리되는지 확인하지 않는다

답을 이진 탐색하려면 "가능한 값들"과 "불가능한 값들"이 경계를 기준으로 나뉘어야 합니다. 어떤 값은 가능하고, 더 큰 값은 불가능했다가, 다시 더 큰 값은 가능해지는 식이라면 이진 탐색을 사용할 수 없습니다.

답의 범위를 정하기 전에 먼저 다음 질문을 해 보세요.

1. 후보 값 x를 정했을 때 가능 여부를 판단할 수 있는가?

2. x가 가능하면 더 큰 값도 가능한가, 아니면 더 작은 값도 가능한가?

3. 가능과 불가능 사이에 하나의 경계가 생기는가?

이 세 질문에 답할 수 있으면 이진 탐색으로 풀 수 있는 문제인지 판단하기 쉬워집니다.

정리

이진 탐색은 하나씩 찾는 습관에서 벗어나, 후보 범위를 절반씩 줄이는 사고법입니다. 단순히 코드 모양을 외우는 것보다 "왜 한쪽을 버릴 수 있는가?"를 이해하는 것이 중요합니다.

정렬된 배열에서 값을 찾을 때는 left, right, mid를 이용해 범위를 줄입니다. 중복된 값이 있다면 존재 여부, 첫 번째 위치, 마지막 위치를 구분해야 합니다. 더 나아가 정답 후보에 대해 "가능한가?"를 판정할 수 있다면, 최솟값이나 최댓값을 찾는 문제에도 이진 탐색을 적용할 수 있습니다.

핵심은 항상 같습니다.

남길 범위와 버릴 범위를 분명히 정한다.

이 기준이 명확하면 이진 탐색은 매우 강력하고 안정적인 도구가 됩니다.