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 Rust DSA version keeps the same data and final output as every other DSA book in this wave.

Basic Implementation

basic.rs
Replay: real traced execution (multi-file project)
fn search(arr: &[i32], target: i32, lo: i32, hi: i32) -> i32 {
	if lo > hi {
		return -1;
	}
	let mid = lo + (hi - lo) / 2;
	if arr[mid as usize] == target {
		return mid;
	}
	if arr[mid as usize] < target {
		return search(arr, target, mid + 1, hi);
	}
	search(arr, target, lo, mid - 1)
}

fn main() {
	let arr = [1, 3, 5, 7, 9, 11, 13];
	let target = 11;
	println!("{}", search(&arr, target, 0, (arr.len() as i32) - 1));
}

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

    1fn search(arr: &[i32], target: i32, lo: i32, hi: i32) -> i32 {2	if lo > hi {
    values this step0lo6hi11target

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

    4}5let mid = lo + (hi - lo) / 2;6if arr[mid as usize] == target {
    values this step3mid7arr[mid](4, 6)next call0lo6hi

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

    4}5let mid = lo + (hi - lo) / 2;6if arr[mid as usize] == target {
    values this step5mid11arr[mid]5result4lo6hi

  4. stdout ← 5

    17	let target = 11;18	println!("{}", search(&arr, target, 0, (arr.len() as i32) - 1));19}
    values this step5stdout5result

Complexity

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

Implementation notes

  • main uses a fixed sorted array, let arr = [1, 3, 5, 7, 9, 11, 13], and passes it as &arr to the recursive function.
  • The signature is fn search(arr: &[i32], target: i32, lo: i32, hi: i32) -> i32. The slice is borrowed read-only, while the search bounds are signed integers.
  • The base case if lo > hi { return -1; } uses -1 as the not-found sentinel; this checked source does not return Option.
  • mid is computed as lo + (hi - lo) / 2, then cast with mid as usize for arr[mid as usize]. The base case keeps negative bounds from being indexed.
  • Branch order checks equality first and returns mid on a hit. If arr[mid] < target, the right call is search(arr, target, mid + 1, hi); otherwise the left call is search(arr, target, lo, mid - 1).
  • Signed bounds avoid usize underflow when forming mid - 1; recursive stack frames carry the borrowed slice, target, and current lo/hi.
  • The trace records the initial call (0, 6), then mid=3 with value 7 and next call (4, 6). In that frame mid=5 matches 11 and returns 5.
  • println!("{}", search(...)) uses display formatting and prints 5.