[백준 2110] 공유기 설치 (Binary Search) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
 
long long N, C;
long long house[200010];
 
long long cal(long long mid)
{
    long long cnt = 1;
    int beforeWifi = 1;
    
    for(int i = 2; i <= N; i++)
    {
        if(house[i] - house[beforeWifi] >= mid)
        {
            cnt++;
            beforeWifi = i;
        }
    }
    
    return cnt; 
}
 
int main(void)
{
//    freopen("B2110_input.txt", "r", stdin);
 
    cin >> N >> C;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> house[i];
    } 
    sort(house+1, house+N+1);
    
    long long left = 1;
    long long right = house[N]-house[1];
    long long Max = 0;
    
    while(left <= right)
    {
        // 공유기 사이의 거리 
        long long mid = (left + right) / 2;
        
        // 설치한 공유기 수 
        long long wifi = cal(mid);
        
        if(wifi >= C)
        {
            if(Max < mid)
            {
                Max = mid;
            }
            
            left = mid+1;
        }
        else if(wifi < C)
        {
            right = mid-1;
        }
    }
    
    cout << Max;
 
    return 0;
}