이분 탐색(Binary Search) 완전 정복 - 개념부터 백준 문제까지

목차

1. 이분 탐색이란?
2. 기본 구현 — 직접 짜는 이분 탐색
3. STL — lower_bound / upper_bound
4. 매개변수 탐색(Parametric Search)
5. 백준 문제 풀이

 

✏️ 1. 이분 탐색이란?

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때, 탐색 범위를 절반씩 줄여가며 탐색하는 알고리즘으로, 선형 탐색은 최악의 경우 배열의 모든 원소를 확인해야 하지만, 이분 탐색은 매 단계마다 탐색 범위를 절반으로 줄이기 때문에 훨씬 빠르다.

이분 탐색은 반드시 정렬된 상태의 배열에서만 적용 가능하므로 정렬되어 있지 않다면 탐색 전에 먼저 정렬해야 한다.
N = 1,000,000일 때 선형 탐색은 최대 1,000,000번 비교하지만, 이분 탐색은 최대 약 20번만 비교하면 된다. 

방식	시간 복잡도(최선)	시간 복잡도(최악)	공간 복잡도
선형 탐색	O(1)	O(N)	O(1)
이분 탐색	O(1)	O(log N)	O(1)

동작 원리

배열 [1, 3, 5, 7, 9, 11, 13]에서 7을 찾는 예시

1. start=0, end=6 → mid=3, arr[3]=7 → target과 일치 → 탐색 성공
2. 만약 arr[mid] < target이면 start = mid + 1 (오른쪽 절반 탐색)
3. 만약 arr[mid] > target이면 end = mid - 1 (왼쪽 절반 탐색)

 

✏️ 2. 기본 구현 

이분 탐색을 구현할 때는 strat, end, mid 세 포인터를 사용한다. [start, end] 닫힌 구간 방식이 가장 보편적이다. 
mid 계산 시 오버플로우 mid = (start + end) / 2 로 쓰면 start + end가 int 범위를 넘을 수 있으므로
mid = start + (end - start) / 2 로 작성하는 습관을 들이자.

// 정렬된 배열 arr에서 target의 인덱스를 반환, 없으면 -1
int binarySearch(vector<int> &arr, int target)
{
    int start = 0, end = arr.size() - 1;

    while (start <= end)
    {
        int mid = start + (end - start) / 2; // overflow 방지

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            start = mid + 1;
        else
            end = mid - 1;
    }
    return -1;
}

 

✏️ 3. STL — lower_bound / upper_bound

 

C++ STL에는 이분 탐색을 내부적으로 수행하는 함수가 두 가지 제공된다.

함수	반환값	설명
lower_bound(first, last, val)	val 이상인 첫 번째 위치	val보다 작은 원소는 모두 앞에 있음
upper_bound(first, last, val)	val 초과인 첫 번째 위치	val 이하인 원소는 모두 앞에 있음

// 사용 예시
vector<int> v = {1, 3, 3, 5, 7, 9};

auto lb = lower_bound(v.begin(), v.end(), 3);  // v[1] 가리킴
auto ub = upper_bound(v.begin(), v.end(), 3);  // v[3] 가리킴

// 값 3이 몇 개인지 → ub - lb = 2
cout << (ub - lb) << "\n";

// 인덱스로 변환
cout << (lb - v.begin()) << "\n";  // 1 출력

 

✏️ 4. 매개변수 탐색 (Parametric Search)

 

이분 탐색을 특정 조건을 만족하는 최솟값/최댓값을 구하는 데 활용하는 기법이다. 단순히 값을 찾는 것을 넘어, 답이 단조적인 특성을 가질 때 넓은 범위에서 이분 탐색으로 최적값을 찾는다.
조건 함수 f(x)가 어떤 경계값 K를 기준으로 x < K → f(x) = false, x ≥ K → f(x) = true 형태일 때 이분 탐색으로 그 경계 K를 O(log N)에 찾는다.

// 조건을 만족하는 최솟값 구하기
long long start = MIN_VAL, end = MAX_VAL, ans = hi;

while (start < = end)
{
    long long mid = start + (end - start) / 2;
    if (check(mid))
    { // 조건 만족
        ans = mid;
        end = mid - 1; // 더 작은 값도 가능한지 탐색
    }
    else
    {
        start = mid + 1;
    }
}
// ans = 조건을 만족하는 최솟값

✏️ 5. 백준 문제 풀이

[BOJ  1920] 수 찾기 - Silver 4

문제 분석

N개의 정수 집합에서 M개의 쿼리를 처리하며 각 쿼리의 수가 집합에 존재하는지 판별한다. N, M ≤ 100,000이므로 단순 선형 탐색 O(NM) = O(10¹⁰)은 시간 초과. 정렬 후 이분 탐색 O((N+M)logN)을 적용한다.

 

풀이 핵심

1. N개의 수를 벡터에 저장 후 sort()로 정렬
2. 각 쿼리마다 binary_search로 존재 여부 확인

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<long long> v;
int findNum(long long num)
{
    int start = 0, end = v.size() - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (num > v[mid])
            start = mid + 1;
        else if (num < v[mid])
            end = mid - 1;
        else
            return 1;
    }
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        long long num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        long long temp;
        cin >> temp;
        cout << findNum(temp) << '\n';
    }
}

---

[BOJ 10816] 숫자 카드 2 - Silver 4

문제 분석

N개의 숫자 카드 중 M개의 쿼리에 대해 각 수가 몇 번 등장하는지 출력한다. 이분 탐색과 카운팅 정렬을 이용하면 쉽게 풀 수 있다.

 

풀이 핵심

1. 입력을 받는 시점부터 각 값들에 대한 개수를 카운팅
2. 각각의 값들에 대해서 이분 탐색을 하면서 해당 값의 위치 획득
3. 1에서 저장했던 카운팅 값을 return

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<long long> v;
int arr[20000001];
int findNum(long long num)
{
    int start = 0, end = v.size() - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (num > v[mid])
            start = mid + 1;
        else if (num < v[mid])
            end = mid - 1;
        else
            return arr[num + 10000000];
    }
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        long long num;
        cin >> num;
        v.push_back(num);
        arr[num + 10000000]++;
    }
    sort(v.begin(), v.end());

    cin >> m;
    for (int i = 0; i < m; i++)
    {
        long long temp;
        cin >> temp;
        cout << findNum(temp) << ' ';
    }
}

 

 

[BOJ 2805] 나무 자르기 - Silver 2

문제 분석

절단기 높이 H를 설정하면 H보다 큰 나무들의 윗부분이 잘린다. 잘린 나무 합이 M 이상이 되는 H의 최댓값을 구한다. 이는 매개변수 탐색의 전형적인 예시다.

나무 높이 최대값 = 2,000,000,000이므로 잘린 합을 구할 때 long long을 반드시 사용해야 한다.

 

풀이 핵심

1. H를 0 ~ max_height 범위에서 이분 탐색
2. check(H): H로 잘랐을 때 얻는 나무 합 ≥ M 인지 확인
3. 조건 만족 시 ans = H로 갱신하고 lo를 올려 더 큰 H 탐색
4. 잘린 나무 합 계산 시 long long 사용 필수

전체 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> tree;

bool check(long long h) {
    long long total = 0;
    for (int t : tree) {
        if (t > h) total += t - h;
    }
    return total >= m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    tree.resize(n);
    for (auto& x : tree) cin >> x;

    long long lo = 0, hi = *max_element(tree.begin(), tree.end());
    long long ans = 0;

    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (check(mid)) {
            ans = mid;   // 조건 만족 → 더 큰 H도 가능한지 확인
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

---

[BOJ  2110] 공유기 설치 - Gold 4

문제 분석

N개의 집 중 C개의 집에 공유기를 설치할 때, 인접한 공유기 사이의 최소 거리를 최대화하는 문제다. 이분 탐색의 대표적인 최솟값의 최댓값 유형이다.

 

풀이 핵심

1. 집 좌표를 오름차순 정렬
2. D를 1 ~ max 범위에서 탐색
3. v2에 각 집들의 좌표 저장
4. c개 이상을 찾은 경우 인접한 집들의 최대 거리 구하기 + 오른쪽 범위 이동, 그렇지 않다면 왼쪽 범위로 이동

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, c;
    cin >> n >> c;

    vector<long long> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    sort(v.begin(), v.end());
    long long start = 1, end = v[n - 1], result = 1;

    while (start <= end)
    {
        // 공유기 사이의 거리 구하기
        long long mid = (start + end) / 2;
        long long tempCount = 0, temp;
        long long tempMax = 1000000000000;

        // v2에 각 집들의 좌표 저장
        vector<long long> v2;
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
            {
                temp = v[0];
                tempCount++;
                v2.push_back(v[0]);
                continue;
            }
            if (temp + mid > v[i])
                continue;
            temp = v[i];
            tempCount++;
            v2.push_back(v[i]);
        }

        // c개 이상을 찾은 경우
        if (tempCount >= c)
        {
            // 인접한 집들의 최대 거리 구하기
            for (int i = 1; i < v2.size(); i++)
            {
                long long dif = v2[i] - v2[i - 1];
                tempMax = min(tempMax, dif);
            }
            result = max(result, tempMax);

            start = mid + 1;
        }
        else
            end = mid - 1;
    }

    cout << result;
}

---

[BOJ  1654] 랜선 자르기 - Silver 2

문제 분석

K개의 랜선을 길이 L로 자를 때 N개 이상을 만들 수 있는 L의 최댓값을 구한다. 나무 자르기와 유사한 매개변수 탐색 문제다.

주의: 랜선 길이 최대 2³¹-1이므로  long long 필수.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, n;
    cin >> k >> n;

    vector<long long> v(k);
    for (int i = 0; i < k; i++)
        cin >> v[i];

    sort(v.begin(), v.end());

    long long start = 1, end = v[k - 1], result = 0;
    while (start <= end)
    {
        long long mid = (start + end) / 2;
        long long tempCount = 0;
        for (int i = 0; i < k; i++)
        {
            tempCount += v[i] / mid;
        }
        if (tempCount >= n)
        {
            result = max(result, mid);
            start = mid + 1;
        }
        else
            end = mid - 1;
    }

    cout << result;
}

---

[BOJ  2805] 나무 자르기 - Silver 2

문제 분석

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

vector<long long> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long m;
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        long long tree;
        cin >> tree;
        v.push_back(tree);
    }

    sort(v.begin(), v.end());

    long long start = 0, end = v[n - 1], result = -1;
    while (start <= end)
    {
        // mid값은 절단기에 설정할 수 있는 높이의 최댓값
        long long mid = (start + end) / 2;
        long long temp = 0;

        // 잘려나가는 나무들의 합
        for (int i = 0; i < n; i++)
        {
            if (mid < v[i])
                temp += v[i] - mid;
        }

        // 나무를 자른 값의 합이 m보다 더 크다면, result값 갱신
        if (temp >= m)
        {
            result = max(result, mid);
            start = mid + 1;
        }

        // 나무즐 자른 값의 합이 m보다 더 작다면, start값을 이동
        else
            end = mid - 1;
    }

    cout << result;
}

---

[BOJ  1300] K번째 수 - Gold 2

문제 분석

N×N 크기의 배열 A가 있고, A[i][j] = i × j일 때 이 배열을 1차원으로 펼쳐 정렬했을 때 K번째 수를 구하는 문제다. 배열을 실제로 만들면 N이 최대 100,000이므로 N² = 10¹⁰ 크기가 되어 메모리 초과. "mid 이하인 수의 개수가 K개 이상인가?" 라는 조건으로 매개변수 탐색을 적용한다.

 

핵심 관찰

i번째 행에서 mid 이하인 수의 개수는 min(mid / i, N)개다. 이를 모든 행에 대해 합산하면 O(N)에 mid 이하인 수의 개수를 구할 수 있다.

 

풀이 핵심

1. 이분 탐색 범위: start=1, end=K (K번째 수는 K를 넘을 수 없음)
2. mid 이하인 수의 개수가 K개 이상인지 확인
3. i번째 행에서 mid 이하인 수의 개수 = min(mid / i, N)
4. 조건 만족 시 ans = mid, end를 내려 더 작은 값 탐색 (최솟값 구하기)

 

전체 코드

#include <iostream>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, k;
    cin >> n >> k;

    long long start = 1, end = k, ans = k;
    while (start <= end)
    {
        long long mid = (start + end) / 2;

        long long count = 0;
        for (long long i = 1; i <= n; i++)
            count += min(mid / i, n);

        if (count >= k)
        {
            ans = mid;
            end = mid - 1;
        }
        else
            start = mid + 1;
    }
    cout << ans;
}

 

---

[BOJ  12015] 가장 긴 증가하는 부분 수열 - Gold 2

문제 분석

수열이 주어졌을 때 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하는 문제다. 일반적인 DP 풀이는 O(N²)인데, N이 최대 1,000,000이므로 시간 초과. 이분 탐색을 활용한 O(N log N) LIS를 적용해야 한다.

 

핵심 아이디어

별도의 배열 v를 유지하는데, v[i]는 길이가 i+1인 증가 부분 수열의 마지막 원소 중 가장 작은 값을 저장한다. 새로운 원소를 처리할 때 dp에서 lower_bound로 삽입 위치를 찾아 교체하면, dp의 길이가 곧 LIS의 길이가 된다.

 

동작 예시 — 수열 [3, 5, 6, 2, 5, 4, 19, 5, 6] 처리 과정

원소 3  → dp: [3]
원소 5  → dp: [3, 5]
원소 6  → dp: [3, 5, 6]
원소 2  → dp: [2, 5, 6]        ← lower_bound(2) = 0번 위치 교체
원소 5  → dp: [2, 5, 6]        ← lower_bound(5) = 1번 위치, 같으므로 교체
원소 4  → dp: [2, 4, 6]        ← lower_bound(4) = 1번 위치 교체
원소 19 → dp: [2, 4, 6, 19]
원소 5  → dp: [2, 4, 5, 19]    ← lower_bound(5) = 2번 위치 교체
원소 6  → dp: [2, 4, 5, 6]     ← lower_bound(6) = 3번 위치 교체

 

 

전체 코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x, idx;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> x;

        int start = 0, end = v.size();
        while (start < end)
        {
            int mid = (start + end) / 2;
            if (v[mid] < x)
                start = mid + 1;
            else
                end = mid;
        }
        // start = x이상인 첫 번재 위치
        if (start == v.size())
            v.push_back(x);
        else
            v[start] = x;
    }
    cout << v.size();
}

✏️  정리

문제	유형핵심	사용 기법
값 존재 여부	정렬 후 탐색	binary_search / lower_bound
값 개수 세기	upper - lower	lower_bound + upper_bound
최솟값의 최댓값 / 최댓값의 최솟값	check 함수 설계가 핵심	매개변수 탐색

이분 탐색 체크리스트

1. 배열/범위가 정렬되어 있거나 단조적인가?
2. lo, hi 초기값이 답의 범위를 완전히 포함하는가?
3. mid = start + (end - lo) / 2 로 오버플로우를 방지했는가?
4. long long이 필요한 범위인가?
5. while 종료 조건이 start <= end 인지 확인했는가?