Binary Search First Occurrence

Find the first copy of a duplicated target by recording matches and continuing to search the left half.

Algorithm

Basic Implementation

basic.pl

use strict;
use warnings;
my @arr = (1, 2, 4, 4, 4, 7, 9);
my $target = 4;
my $lo = 0;
my $hi = $#arr;
my $result = -1;
while ($lo <= $hi) {
	my $mid = int($lo + ($hi - $lo) / 2);
	if ($arr[$mid] == $target) {
		$result = $mid;
		$hi = $mid - 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

Keep the explicit control flow. Library shortcuts would hide the state changes this lesson is meant to replay.
The final output is intentionally small and deterministic for cross-language comparison.

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

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