Binary Search (Iterative)

On a sorted array, narrow [lo, hi] window by halving until $arr[$mid] equals the target or the window is empty. Demonstrates the "discard half the search space" invariant.

Algorithm

Canonical input @arr = (1, 3, 5, 7, 9, 11, 13) with $target = 11 finishes in two frames: descend right to $mid = 5, match.

Basic Implementation

basic.pl

use strict; use warnings;
use integer;
my @arr = (1, 3, 5, 7, 9, 11, 13);
my $target = 11;
my $lo = 0;
my $hi = scalar(@arr) - 1;
my $result = -1;
my $done = 0;
while (!$done && $lo <= $hi) {
	my $mid = $lo + ($hi - $lo) / 2;
	if ($arr[$mid] == $target) {
		$result = $mid;
		$done = 1;
	} elsif ($arr[$mid] < $target) {
		$lo = $mid + 1;
	} else {
		$hi = $mid - 1;
	}
}
print "$result\n";

Complexity

Time: O(log n)
Space: O(1)

Implementation notes

Perl: use integer; at the top of the file forces integer division for /, so $mid = $lo + ($hi - $lo) / 2 returns an integer directly rather than the floating-point result Perl's / operator otherwise produces. Computing $mid = $lo + ($hi - $lo) / 2 rather than ($lo + $hi) / 2 keeps the lesson aligned with overflow-safe practice across languages.
A small $done = 0 flag plus !$done && $lo <= $hi keeps the match-and-exit path visible without leaning on last.
The replay highlights the [$lo, $hi] window, marks $mid, and labels the branch taken (left half / right half / match).

midpoint `$mid = $lo + ($hi - $lo) / 2` (overflow-safe integer division under the `use integer;` pragma).

inclusive window `$hi` is inclusive. The loop runs while `$lo <= $hi`.