Recursion and half-open range reasoning

The idea

Recursive algorithms need a base case and a smaller subproblem on every path. For sequences, [lo, hi) expresses an empty range when lo equals hi and avoids a special negative index for empty input. Keep indexes within the container’s valid range before reading an element; the one-past-end position is useful as a boundary but is not an element.

A lower-bound search on sorted values finds the first element not less than a target. If the midpoint is smaller, discard it and all earlier candidates; otherwise keep it in the left range. The range shrinks at each step. This yields logarithmic recursion depth, while a recursive walk removing only one element at a time has linear depth and can be better implemented as a loop.

#include <iostream>
#include <vector>
#include <cstddef>
std::size_t lower(const std::vector<int>& a, int x, std::size_t lo, std::size_t hi) {
  if (lo == hi) return lo;
  auto mid = lo + (hi - lo) / 2;
  return a[mid] < x ? lower(a, x, mid + 1, hi) : lower(a, x, lo, mid);
}
int main() { std::vector<int> a{1,4,4,8}; std::cout << lower(a,4,0,a.size()); }

1

The equal midpoint remains a candidate while the search checks earlier positions.