[알고리즘] 27. 이분 탐색 응용

지난 글에서는 이분 탐색 기초에 대해 정리했습니다. 이번 글에서는 단순히 특정 값을 찾는 것을 넘어, 이분 탐색을 조금 더 넓게 활용하는 방법을 알아보겠습니다.

이분 탐색은 정렬된 배열에서 값을 찾을 때만 사용하는 알고리즘처럼 보일 수 있습니다. 하지만 실제 알고리즘 문제에서는 조건을 만족하는 가장 작은 값이나 조건을 만족하는 가장 큰 값을 찾을 때도 자주 사용됩니다.

이분 탐색 응용의 핵심은 값을 직접 찾는 것이 아니라, 조건을 만족하는 경계 지점을 찾는 것입니다.

1. 기본 이분 탐색과 응용 이분 탐색의 차이

기본 이분 탐색은 정렬된 배열에서 target 값이 있는지 찾는 방식입니다.

정렬된 배열: [1, 3, 5, 7, 9]
target = 7
결과: 인덱스 3

하지만 응용 이분 탐색에서는 꼭 target과 정확히 같은 값을 찾지 않을 수도 있습니다. 대신 아래와 같은 값을 찾습니다.

target 이상이 처음 나오는 위치
target보다 큰 값이 처음 나오는 위치
조건을 만족하는 가장 작은 값
조건을 만족하는 가장 큰 값
가능한 답의 최솟값
가능한 답의 최댓값

즉 단순히 “같은 값 찾기”에서 끝나는 것이 아니라, 조건이 바뀌는 지점을 찾는 데 이분 탐색을 사용할 수 있습니다.

2. 경계 지점이란?

이분 탐색 응용에서 자주 나오는 표현이 경계 지점입니다. 경계 지점은 조건의 결과가 바뀌는 위치를 의미합니다.

예를 들어 정렬된 배열에서 6 이상인 값이 처음 나오는 위치를 찾는다고 하겠습니다.

배열: [1, 3, 5, 7, 9, 11]
조건: 값이 6 이상인가?

각 값에 조건을 적용하면 다음과 같습니다.

값	1	3	5	7	9	11
6 이상?	false	false	false	true	true	true

false가 이어지다가 7부터 true로 바뀝니다. 이때 true가 처음 시작되는 위치가 경계 지점입니다.

이분 탐색 응용은 false와 true가 바뀌는 경계를 찾는 문제로 생각할 수 있습니다.

3. target 이상이 처음 나오는 위치 찾기

정렬된 배열에서 target 이상인 값이 처음 나오는 위치를 찾는 문제를 보겠습니다. 이 방식은 lower bound와 비슷한 개념입니다.

배열: [1, 3, 5, 7, 9, 11]
target = 6

6 이상인 첫 값: 7
위치: 인덱스 3

Java 코드로 작성하면 다음과 같습니다.

int[] arr = {1, 3, 5, 7, 9, 11};
int target = 6;

int left = 0;
int right = arr.length - 1;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] >= target) {
        answer = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

System.out.println(answer);

출력 결과는 다음과 같습니다.

arr[3]은 7입니다. 7은 target 6 이상인 첫 번째 값입니다.

조건을 만족했을 때 바로 끝내지 않고, 더 왼쪽에도 가능한 값이 있는지 확인하는 것이 핵심입니다.

4. 왜 right = mid - 1을 할까요?

target 이상인 값을 찾았다고 해서 바로 끝내면 안 됩니다. 우리는 단순히 조건을 만족하는 아무 위치가 아니라, 처음으로 조건을 만족하는 위치를 찾고 있기 때문입니다.

if (arr[mid] >= target) {
    answer = mid;
    right = mid - 1;
}

arr[mid]가 조건을 만족했다면 일단 answer에 저장합니다. 하지만 mid보다 왼쪽에도 조건을 만족하는 값이 있을 수 있습니다. 그래서 right를 mid - 1로 줄여 왼쪽 범위를 더 확인합니다.

반대로 arr[mid]가 target보다 작다면 그 위치와 왼쪽은 모두 조건을 만족할 수 없습니다. 그래서 left를 mid + 1로 이동합니다.

arr[mid] >= target → 후보 저장 후 왼쪽 확인
arr[mid] < target  → 오른쪽 확인

5. target보다 큰 값이 처음 나오는 위치 찾기

이번에는 target 이상이 아니라 target보다 큰 값이 처음 나오는 위치를 찾아보겠습니다. 이 방식은 upper bound와 비슷한 개념입니다.

배열: [1, 3, 5, 7, 7, 7, 9]
target = 7

7보다 큰 첫 값: 9
위치: 인덱스 6

Java 코드로 작성하면 다음과 같습니다.

int[] arr = {1, 3, 5, 7, 7, 7, 9};
int target = 7;

int left = 0;
int right = arr.length - 1;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] > target) {
        answer = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

System.out.println(answer);

출력 결과는 다음과 같습니다.

arr[6]은 9입니다. 9가 7보다 큰 첫 번째 값입니다.

6. target 이하가 마지막으로 나오는 위치 찾기

이번에는 반대로 target 이하인 값이 마지막으로 나오는 위치를 찾아보겠습니다.

배열: [1, 3, 5, 7, 9, 11]
target = 8

8 이하인 마지막 값: 7
위치: 인덱스 3

이 경우 조건을 만족하면 더 오른쪽에도 가능한 값이 있는지 확인해야 합니다.

int[] arr = {1, 3, 5, 7, 9, 11};
int target = 8;

int left = 0;
int right = arr.length - 1;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] <= target) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

System.out.println(answer);

출력 결과는 다음과 같습니다.

arr[3]은 7이고, 8 이하인 값 중 가장 오른쪽에 있습니다.

마지막 위치를 찾을 때는 조건을 만족한 뒤 오른쪽을 더 확인합니다.

7. target보다 작은 값이 마지막으로 나오는 위치 찾기

이번에는 target보다 작은 값이 마지막으로 나오는 위치를 찾겠습니다.

배열: [1, 3, 5, 7, 7, 7, 9]
target = 7

7보다 작은 마지막 값: 5
위치: 인덱스 2

Java 코드로 작성하면 다음과 같습니다.

int[] arr = {1, 3, 5, 7, 7, 7, 9};
int target = 7;

int left = 0;
int right = arr.length - 1;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] < target) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

System.out.println(answer);

출력 결과는 다음과 같습니다.

arr[2]는 5입니다. 5는 target 7보다 작은 값 중 가장 마지막 위치에 있습니다.

8. 중복 값 개수 구하기

이분 탐색 응용을 이용하면 정렬된 배열에서 특정 값이 몇 번 등장하는지도 구할 수 있습니다.

예를 들어 배열에 7이 몇 개 있는지 구해보겠습니다.

배열: [1, 3, 5, 7, 7, 7, 9]
target = 7

7의 첫 위치: 3
7보다 큰 첫 위치: 6
개수: 6 - 3 = 3

먼저 target 이상이 처음 나오는 위치를 구합니다. 그다음 target보다 큰 값이 처음 나오는 위치를 구합니다. 두 위치의 차이가 target의 개수입니다.

int[] arr = {1, 3, 5, 7, 7, 7, 9};
int target = 7;

int lower = lowerBound(arr, target);
int upper = upperBound(arr, target);

System.out.println(upper - lower);

public static int lowerBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

public static int upperBound(int[] arr, int target) {
    int left = 0;
    int right = arr.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

출력 결과는 다음과 같습니다.

배열에서 7은 총 3번 등장합니다.

9. right를 arr.length로 두는 방식

이분 탐색 응용에서는 right를 arr.length - 1이 아니라 arr.length로 두는 방식도 자주 사용합니다.

int left = 0;
int right = arr.length;

while (left < right) {
    int mid = left + (right - left) / 2;

    if (arr[mid] >= target) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

이 방식은 탐색 범위를 left 이상, right 미만으로 봅니다. 즉 right 위치는 탐색에 포함되지 않습니다.

방식	초기 right	반복 조건	범위 의미
기본 방식	arr.length - 1	left <= right	양끝 포함
경계 탐색 방식	arr.length	left < right	left 이상, right 미만

둘 다 사용할 수 있지만, 경계 위치를 찾는 문제에서는 left < right 방식이 깔끔할 때가 많습니다.

이분 탐색은 범위를 어떻게 정의했는지에 따라 반복 조건과 갱신 방식이 달라집니다.

10. 정답 범위에서 이분 탐색하기

이분 탐색은 배열에서만 사용하는 것이 아닙니다. 정답이 될 수 있는 범위를 정해두고, 그 범위 안에서 가능한 값을 찾는 방식으로도 사용됩니다.

예를 들어 어떤 값 x가 조건을 만족하는지 확인할 수 있다고 하겠습니다.

x가 너무 작음 → 조건 불만족
x가 충분히 큼 → 조건 만족

이 경우 조건을 만족하는 가장 작은 x를 이분 탐색으로 찾을 수 있습니다.

가능한 정답 범위: 1 ~ 100
조건을 만족하는 가장 작은 값 찾기

이런 유형은 흔히 “정답을 이분 탐색한다”라고 표현합니다.

이분 탐색은 배열뿐 아니라 가능한 정답 범위에도 사용할 수 있습니다.

11. 조건을 만족하는 가장 작은 값 찾기

조건을 만족하는 가장 작은 값을 찾는 기본 형태를 보겠습니다.

예를 들어 x가 15 이상이면 조건을 만족한다고 가정하겠습니다. 가능한 범위는 1부터 30입니다.

int left = 1;
int right = 30;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (check(mid)) {
        answer = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

System.out.println(answer);

public static boolean check(int x) {
    return x >= 15;
}

출력 결과는 다음과 같습니다.

15부터 조건을 만족하므로 가장 작은 만족 값은 15입니다.

조건을 만족하면 answer에 저장하고 더 작은 값도 가능한지 왼쪽을 확인합니다. 조건을 만족하지 않으면 더 큰 값이 필요하므로 오른쪽으로 이동합니다.

12. 조건을 만족하는 가장 큰 값 찾기

이번에는 조건을 만족하는 가장 큰 값을 찾는 경우입니다.

예를 들어 x가 15 이하이면 조건을 만족한다고 가정하겠습니다. 가능한 범위는 1부터 30입니다.

int left = 1;
int right = 30;
int answer = -1;

while (left <= right) {
    int mid = left + (right - left) / 2;

    if (check(mid)) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

System.out.println(answer);

public static boolean check(int x) {
    return x <= 15;
}

출력 결과는 다음과 같습니다.

15 이하까지 조건을 만족하므로 가장 큰 만족 값은 15입니다.

조건을 만족하면 answer에 저장하고 더 큰 값도 가능한지 오른쪽을 확인합니다. 조건을 만족하지 않으면 값을 줄여야 하므로 왼쪽으로 이동합니다.

가장 작은 값을 찾을 때는 만족 후 왼쪽, 가장 큰 값을 찾을 때는 만족 후 오른쪽을 확인합니다.

13. 이분 탐색 응용 문제의 판단 흐름

문제를 보고 이분 탐색을 떠올리려면 아래 흐름으로 생각해보면 좋습니다.

정렬된 데이터에서 위치를 찾아야 하는가?
조건을 만족하는 첫 위치나 마지막 위치를 찾아야 하는가?
가능한 정답의 범위가 정해져 있는가?
어떤 값이 가능한지 check 함수로 판단할 수 있는가?
값이 커질수록 조건 결과가 일정한 방향으로 바뀌는가?

특히 마지막 조건이 중요합니다. 이분 탐색은 조건 결과가 어느 지점부터 false에서 true로 바뀌거나, true에서 false로 바뀌는 구조일 때 사용할 수 있습니다.

false false false true true true
또는
true true true false false false

이런 식으로 한 번 방향이 바뀌는 구조라면 이분 탐색을 적용할 수 있습니다.

14. 이분 탐색 응용의 시간복잡도

이분 탐색은 탐색 범위를 절반씩 줄입니다. 따라서 기본 시간복잡도는 O(log N)입니다.

하지만 check 함수가 따로 있는 경우에는 check 함수의 시간도 함께 고려해야 합니다.

구분	시간복잡도
이분 탐색 반복 횟수	O(log N)
check 함수가 O(1)	전체 O(log N)
check 함수가 O(N)	전체 O(N log N)

정답 범위를 이분 탐색하는 문제에서는 check 함수가 배열 전체를 한 번 확인하는 경우가 많습니다. 그럴 때는 전체 시간복잡도가 O(N log N)이 될 수 있습니다.

이분 탐색 응용에서는 반복 횟수뿐 아니라 check 함수의 비용도 함께 봐야 합니다.

15. 이분 탐색 응용에서 자주 하는 실수

이분 탐색 응용 문제에서는 아래 실수를 자주 하게 됩니다.

조건을 만족하는 아무 값만 찾고 바로 종료하는 경우
가장 작은 값과 가장 큰 값 중 무엇을 찾아야 하는지 헷갈리는 경우
조건을 만족했을 때 left를 움직일지 right를 움직일지 잘못 정하는 경우
answer 변수를 갱신하지 않는 경우
left < right 방식과 left <= right 방식을 섞어서 사용하는 경우
경계값이 배열 밖으로 나가는 경우를 처리하지 않는 경우
check 함수의 true, false 방향을 반대로 이해하는 경우

가장 중요한 것은 내가 찾는 값이 첫 번째 만족 값인지, 마지막 만족 값인지 먼저 정하는 것입니다.

첫 번째 만족 값 → 조건 만족 시 왼쪽 확인
마지막 만족 값 → 조건 만족 시 오른쪽 확인

이분 탐색 응용은 탐색 방향을 잘못 잡으면 정답이 한 칸씩 밀리기 쉽습니다.

16. 정리

이번 글에서는 이분 탐색 응용에 대해 정리했습니다.

이분 탐색은 단순히 같은 값을 찾는 데만 사용하지 않는다.
조건을 만족하는 첫 위치나 마지막 위치를 찾을 수 있다.
target 이상이 처음 나오는 위치는 lower bound와 비슷한 개념이다.
target보다 큰 값이 처음 나오는 위치는 upper bound와 비슷한 개념이다.
중복 값의 개수는 upper bound - lower bound로 구할 수 있다.
배열이 아니라 가능한 정답 범위에서도 이분 탐색을 사용할 수 있다.
조건을 만족하는 가장 작은 값과 가장 큰 값을 구분해야 한다.
check 함수가 있는 경우 전체 시간복잡도는 check 비용까지 고려해야 한다.

이분 탐색 응용은 처음에는 헷갈리기 쉽습니다. 하지만 핵심은 항상 같습니다. 정렬된 구조나 가능한 답의 범위에서 조건이 바뀌는 경계 지점을 찾는 것입니다.

이분 탐색 응용의 핵심은 “가능한 범위 안에서 조건을 만족하는 경계값을 찾는 것”입니다.

다음 글 예고

다음 글에서는 DFS에 대해 알아보겠습니다.

한 방향으로 깊게 탐색하는 방식, 재귀를 이용한 DFS, 방문 배열, 그래프 탐색의 기본 흐름을 예제로 정리해보겠습니다

'Problem Solving > Algorithm' 카테고리의 다른 글

[알고리즘] 29. BFS 너비 우선 탐색 (0)	2026.07.12
[알고리즘] 28. DFS 깊이 우선 탐색 (1)	2026.07.11
[알고리즘] 26. 이분 탐색 기초 (0)	2026.07.09
[알고리즘] 25. 선형 탐색(Linear Search) (0)	2026.07.09
[알고리즘] 24. 유니온 파인드(Union-Find) (0)	2026.07.07