+C++ example
In C++20, std::span<const int> and std::size_t express the same half-open interval $[\text{lo}, \text{hi})$ without copying the underlying container. Unsigned integer division lo + (hi - lo) / 2 truncates toward zero and produces the same boundary index as 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();
// Invariant: values[0..lo) < target and 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);
// An insertion boundary still needs an in-bounds equality check.
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;
}
Output:
1
3
-1