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

my @arr = (1, 2, 4, 4, 4, 7, 9) declares the sorted Perl array with the @ sigil.
my $target = 4 and the search bounds $lo, $hi, and $result are scalar variables.
$hi = $#arr uses Perl's last-index form, so the first window is indexes 0 through 6.
$result = -1 is the not-found sentinel until a match is recorded.
The loop continues while ($lo <= $hi).
The midpoint uses integer truncation: int($lo + ($hi - $lo) / 2).
Each probe reads a scalar element with $arr[$mid].
Comparisons are numeric: == for a match and < for deciding whether to move the left bound right.
On a match, the code stores $result = $mid and then sets $hi = $mid - 1, which keeps searching left for the first occurrence.
The trace starts with lo = 0, hi = 6, and result = -1.
First probe: mid = 3 matches 4, so result becomes 3 and hi moves to 2.
Second probe: mid = 1 reads 2, so lo moves to 2 and result stays 3.
Third probe: mid = 2 matches 4, so result becomes 2 and hi moves to 1.
The loop stops once lo > hi, and print "$result\n" outputs 2.

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.