Searching

Binary Search (Recursive)

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

Algorithm

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.

Basic Implementation

basic.cpp
Replay: real traced execution (multi-file project)
#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;
}

  1. lo ← 0, hi ← 6, target ← 11

    1#include <iostream>2#include <unordered_map>
    values this step0lo6hi11target

  2. mid ← 3, arr[mid] ← 7, next call ← (4, 6)

    6if (lo > hi) return -1;7int mid = lo + (hi - lo) / 2;8if (arr[mid] == target) return mid;
    values this step3mid7arr[mid](4, 6)next call0lo6hi

  3. mid ← 5, arr[mid] ← 11, result ← 5

    6if (lo > hi) return -1;7int mid = lo + (hi - lo) / 2;8if (arr[mid] == target) return mid;
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    1#include <iostream>2#include <unordered_map>
    values this step5stdout5result

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.