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

use strict;
use warnings;
my @arr = (1, 3, 5, 7, 9, 11, 13);
my $target = 11;
sub search {
	my ($lo, $hi) = @_;
	return -1 if $lo > $hi;
	my $mid = int($lo + ($hi - $lo) / 2);
	return $mid if $arr[$mid] == $target;
	return search($mid + 1, $hi) if $arr[$mid] < $target;
	return search($lo, $mid - 1);
}
print search(0, $#arr), "\n";

Complexity

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

Implementation notes

my @arr = (1, 3, 5, 7, 9, 11, 13) declares the sorted Perl array with the @ sigil.
my $target = 11 stores the searched value as a scalar.
sub search takes only bounds: my ($lo, $hi) = @_.
The subroutine closes over the surrounding @arr and $target; it does not pass the array by value or by reference.
The base case is return -1 if $lo > $hi.
The midpoint uses integer truncation: int($lo + ($hi - $lo) / 2).
Each probe reads the array with scalar element syntax, $arr[$mid].
Comparisons are numeric: == for the match and < to choose the right half.
A match returns immediately with return $mid.
If the probed value is smaller than the target, the recursive branch is search($mid + 1, $hi).
Otherwise the branch is search($lo, $mid - 1).
The initial call is search(0, $#arr), where $#arr is the last index, 6.
The trace first checks lo = 0, hi = 6, computes mid = 3, reads 7, and recurses right to (4, 6).
The next call computes mid = 5, reads 11, and returns index 5.
That return value propagates back to the top-level print search(...), "\n" call, which outputs 5.

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

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