+C++ 예제
C++20에서는 연속된 메모리를 소유권 복사 없이 받는 std::span<const int>와 부호 없는 인덱스 std::size_t로 같은 반열린 구간 $[\text{lo}, \text{hi})$를 표현할 수 있다. 정수 나눗셈 lo + (hi - lo) / 2가 곧바로 내림($\lfloor(\text{hi} - \text{lo}) / 2\rfloor$)이 되며, 표준 라이브러리의 std::lower_bound와 동일한 경계 인덱스를 돌려준다.
#include <cstddef>
#include <iostream>
#include <span>
#include <vector>
std::size_t lowerBound(std::span<const int> values, int target) {
std::size_t lo = 0;
std::size_t hi = values.size();
// 불변식: values[0..lo) < target 이고 values[hi..n) >= target
while (lo < hi) {
std::size_t mid = lo + (hi - lo) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
int indexOfSorted(std::span<const int> values, int target) {
std::size_t index = lowerBound(values, target);
// 삽입 경계 인덱스가 범위 안이고 실제 값이 일치하는지 확인한다.
return index < values.size() && values[index] == target
? static_cast<int>(index)
: -1;
}
int main() {
const std::vector<int> values{1, 3, 3, 7, 9};
std::cout << lowerBound(values, 3) << '\n';
std::cout << lowerBound(values, 6) << '\n';
std::cout << indexOfSorted(values, 6) << '\n';
return 0;
}
실행 결과:
1
3
-1