이분탐색에서 구간 [lo, hi]에 답이 없는 경우는 예외처리할 것

lo와 hi 범위 안에 avail이 true인게 반드시 존재해야 함. 그렇지 않으면 예외처리 할 것.

// binary search sudo code
lo, hi ← (답이 될 수 있는 가장 작은 값), (답이 될 수 있는 가장 큰 값)
ans ← (답이 될 수 없는 값)
while lo ≤ hi:
    mid = (lo+hi)/2
    if avail(mid):
        ans = mid
        hi = mid - 1
        // 경우에 따라 lo = mid + 1
    else:
        lo = mid + 1
        // 경우에 따라 hi = mid - 1

Problem - E - Codeforces

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define all(v) v.begin(), v.end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
 
ll N, M;
map<ll, ll> mp;
vector<ll> v;
 
bool avail(ll x, ll lb)
{
    ll cnt = 0;
    ll p = 0;
    while(p < M && cnt < lb){
        auto it = lower_bound(v.begin()+p, v.end(), x);
        if(it != v.end()){
            cnt += 1;
            p = it-v.begin()+1;
            x *= 2;
        }
        else break;
    }
 
    return cnt >= lb;
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    cin >> N;
    for(ll i = 0; i < N; ++i){
        ll x; cin >> x;
        mp[x] += 1;
    }
   
    for(auto& [val, cnt]: mp){
        v.emplace_back(cnt);
    }
    sort(all(v));
 
    M = v.size();
    ll ans = 0;
    for(ll i = 1; i <= M; ++i){
        ll lo = 1, hi = v[M-1];
        ll x = -1;
        while(lo <= hi){
            ll mid = (lo+hi)/2;
            if(avail(mid, i)){
                x = mid;
                lo = mid+1;
            }
            else hi = mid-1;
        }
 
        if(x != -1) ans = max(ans, x*((1LL<<i)-1));
        // 틀림 ans = max(ans, x*((1LL<<i)-1));
    }
    cout << ans << endl;
 
    return 0;
}cs