Binary Search (Recursive)

Use the same binary-search window as the iterative lesson, but pass lo and hi through recursive calls.

Algorithm

Basic Implementation

basic.cpp

#include <iostream>
#include <unordered_map>
#include <vector>

int search(const std::vector<int>& arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return search(arr, target, mid + 1, hi);
    return search(arr, target, lo, mid - 1);
}

int main() {
    std::vector<int> arr{1, 3, 5, 7, 9, 11, 13};
    int target = 11;
    std::cout << search(arr, target, 0, static_cast<int>(arr.size()) - 1) << "\n";
    return 0;
}

Complexity

Time: O(log n)
Space: O(log n) call stack

Implementation notes

In C++, the input is a std::vector<int> initialized as {1, 3, 5, 7, 9, 11, 13} and passed to search(const std::vector<int>& arr, int target, int lo, int hi) by const reference, so recursive calls do not copy or mutate the vector.
Bounds are scalar int values. The initial hi is static_cast<int>(arr.size()) - 1, and the base case returns -1 when lo > hi.
The midpoint uses lo + (hi - lo) / 2, producing an int index for arr[mid] without direct lo + hi addition.
Recursive branch returns propagate directly: values below the target call search(arr, target, mid + 1, hi), values above call search(arr, target, lo, mid - 1), and a match returns mid.
The trace records the first call (lo=0, hi=6), mid=3 with value 7 and next call (4, 6), then mid=5 with value 11 returning result 5.
std::cout << search(...) << "\n" writes 5. Visible allocation is the vector storage from the initializer list; runtime state is scalar call-frame data on the recursion stack.

execution replay The checked-in replay follows the language-neutral state table for `search-binary-recursive`.

cross-language comparison This C++ DSA version keeps the same data and final output as every other DSA book in this wave.