이분탐색+백준 2805 C++

이분탐색이란?

정렬된 배열이나 범위에서 원하는 값을 빠르게 찾기 위한 탐색 알고리즘입니다.
전체를 한 번에 다 보지 않고, 중간을 기준으로 반씩 줄여가며 탐색합니다.

• 정렬된 데이터에서만 사용 가능
• 중간값(mid)을 기준으로 왼쪽 or 오른쪽 중 한쪽만 계속 탐색
• 시간복잡도: O(log N) (매우 빠름!)

 

알고리즘 문제에서 구현이 너무 쉽다면 이분탐색을 꼭 꼭 꼭 생각해보자!!!

 

 

이렇게 계속 반으로 쪼갠다.

---

🔧 기본 구조 (코드 예시 - C++)

int binarySearch(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

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

        if (arr[mid] == target)
            return mid; // 찾음!
        else if (arr[mid] < target)
            left = mid + 1; // 오른쪽 탐색
        else
            right = mid - 1; // 왼쪽 탐색
    }

    return -1; // 못 찾음
}

---

어떻게 동작하나?

예: [1, 3, 5, 7, 9, 11] 에서 7을 찾는다고 할 때

1. 처음 mid: 5 (index 2)
2. 7 > 5 → 오른쪽만 탐색 → [7, 9, 11]
3. 다시 mid: 9 (index 4)
4. 7 < 9 → 왼쪽만 탐색 → [7]
5. mid = 7 → 찾음!

---

 

https://www.acmicpc.net/submit/2805/94019627

 

백준 예시 문제

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> v(n);
    int high = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        if (v[i] > high) high = v[i];
    }

    int low = 0;
    int result = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        long long sum = 0;

        for (int i = 0; i < n; i++) {
            if (v[i] > mid) sum += v[i] - mid;
        }

        if (sum >= m) {
            result = mid;  // 조건을 만족했으므로 저장
            low = mid + 1; // 더 큰 값도 가능한지 탐색
        } else {
            high = mid - 1; // 너무 많이 잘랐음
        }
    }

    cout << result << '\n';
    return 0;
}