이분 탐색 (이진 탐색)

이분 탐색

정렬된 배열이나 리스트에서 매 루프마다 탐색 구간을 반으로 쪼개서 시간복잡도를 logN으로 탐색하는 알고리즘.

정렬 되어있다는게 중요하다! 정렬이 안되어있다면 별도로 정렬 후 로직을 실행하자.

 

예시 1) 

주어진 배열에서 특정 값이 존재한다면 인덱스를 반환하는 함수

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

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

    while (left <= right)
    {
        // (left + right) / 2 와 같지만 오버플로우 방지됨
        int mid = left + (right - left) / 2;

        cout << mid << " : " << arr[mid] << endl;

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

    return -1; // 못찾음
}

// int main(void)
int Code::main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> arr = { 1, 2, 3, 5, 10, 21, 22, 24 };
    sort(arr.begin(), arr.end()); // 반드시 정렬해야함

    int target = 3;
    int result = GetIndex(arr, target);
    cout << result; // 못찾으면 -1
    return 0;
}

 

 

이진 탐색 + 최적해 찾기

특정 조건의 최대/최소를  이진 탐색으로 구하기

https://www.acmicpc.net/problem/2792

 

 

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

int n, m;
vector<int> v;
int ret = INT32_MAX;

bool IsPossible(int mid)
{
    int remain = n;
    for (int i : v)
    {
        int cnt = ((i - 1) / mid) + 1;
        remain -= cnt;
    }

    return remain >= 0;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n >> m;

    v.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> v[i];

    int left = 1;
    int right = INT32_MAX;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (IsPossible(mid))
        {
            ret = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    cout << ret;
}

 

조건을 정하고, 조건을 만족하면 더 최적화된 값을 향하는 방향으로 구간을 재설정하면된다.

 

 

 

이진 탐색 + 최적해 찾기 2

다른 스타일의 코드

 

좋은 설명글

https://www.acmicpc.net/blog/view/109

 

예제 문제

https://www.acmicpc.net/problem/1654

 

세 줄 요약

[lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
while (lo + 1 < hi)동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid

 

구한 경계에서 답이 lo인지 hi인지 생각해보고 출력

 

(1에서 경계는 항상 [lo, hi] 내에 존재하고, 2에서 Check(lo), Check(hi)는 변하지 않으며, 3에서 lo + 1 >= hi이고, lo < mid < hi에서 lo < hi이므로 lo + 1 == hi를 만족합니다)

 

 

내 코드

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

int k, n;
vector<int> v;

bool Check(const long long mid)
{
    int sum = 0;
    for (const int& i : v)
        sum += i / mid;

    return sum >= n;
}

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

    cin >> k >> n;
    v.resize(k);

    int temp;
    for (int i = 0; i < k; ++i)
    {
        cin >> temp;
        v[i] = temp;
    }

    long long lo = 0;
    long long hi = (long long)INT32_MAX + 1;
    while (lo + 1 < hi)
    {
        long long mid = (lo + hi) / 2L;
        if (Check(mid))
            lo = mid;
        else
            hi = mid;
    }

    cout << lo << '\n';
}