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.rs

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));
}

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.

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.