이분 탐색

템플릿

let lo = 0, hi = a.length - 1;
while (lo <= hi) {
  const mid = (lo + hi) >> 1;
  if (a[mid] === t) return mid;
  if (a[mid] < t) lo = mid + 1;
  else hi = mid - 1;
}

하한 · 상한

“이상인 첫 위치”는 조건이 참인 쪽을 남기는 변형이 필요합니다.

전제

정렬되어 있어야 합니다. 아니면 먼저 정렬하거나 다른 패턴.

한 줄

> 정렬 + 단조 조건 → 이분.