x와 가장 가까운 수 y 찾기

x와 가장 가까운 수 y의 후보는 

• x보다 큰 수 중 최소
• x보다 작은 수 중 최대

이므로

• lower_bound 결과
• 그보다 하나 앞에 것

만 비교해서 작은 것을 뽑으면 O(logn)에 x와 가장 가까운 수 y를 찾을 수 있다.

---

ll x, y;
ll dist = INF;
vector<ll> v;

auto i = lower_bound(v.begin(), v.end(), x);
if (i != v.end()) if (*i - x < dist)
{
	dist = *i - x;
	y = *i;
}
if (i != v.begin()) if (*(--i) - x < dist)
{
	dist = *i - x;
	y = *i;
}

---

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

(Connecting Two Barns)

이 문제를 풀고 기록해두면 좋을 것 같아 기록해둔다.