−C++20
C++20에서는 오름차순 정수 배열을 const 참조로 받아 복사 없이 읽는다. lowerBound는 삽입 경계를, indexOfSorted는 실제 일치 위치 또는 -1을 반환하며, 아래 TypeScript판과 같은 세 결과를 출력한다.
#include <cstddef>
#include <iostream>
#include <vector>
std::size_t lowerBound(const std::vector<int>& values, int target) {
std::size_t lo = 0;
std::size_t hi = values.size();
// lo 앞의 값은 target 미만, hi부터의 값은 target 이상이다.
while (lo < hi) {
const auto mid = lo + (hi - lo) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
std::ptrdiff_t indexOfSorted(const std::vector<int>& values, int target) {
const auto index = lowerBound(values, target);
// 배열 끝의 삽입 경계도 가능하므로 먼저 범위를 확인한다.
if (index == values.size() || values[index] != target) return -1;
return static_cast<std::ptrdiff_t>(index);
}
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
TypeScript