https://www.acmicpc.net/problem/17266
가로등의 높이는 최소 1, 최대 n이다. 이 범위에서 굴다리를 모두 비추기 위한 가로등의 최소 높이를 빠르게 구하기 위해 이분탐색을 사용하였다.
가로등의 높이를 height이라고 할 때, 가로등을 설치하려는 위치 배열 pos의 어떤 두 원소의 차가 2 * height보다 크면 안 된다.
이 조건을 만족하는 가장 작은 height을 구했다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<int> pos;
bool isValid(int height) {
if(pos[0] > height) return false;
int range = 2 * height;
for(int i=1; i<m; i++) {
if(pos[i] - pos[i-1] > range) return false;
}
if(n - pos[m-1] > height) return false;
return true;
}
int binarySearch() {
int start = 0;
int end = n;
int mid = (start + end) / 2;
int ans = end;
while(start <= end) {
if(isValid(mid)) {
ans = mid;
end = mid - 1;
}
else {
start = mid + 1;
}
mid = (start + end) / 2;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
pos.resize(m);
for(int i=0; i<m; i++) cin >> pos[i];
cout << binarySearch();
return 0;
}