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

Basic Implementation

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

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

    1use strict;2use warnings;
    values this step0lo6hi11target

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

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

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

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

  4. stdout ← 5

    12}13print search(0, $#arr), "\n";
    values this step5stdout5result

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.