Searching

Binary Search First Occurrence

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

Algorithm

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.

Basic Implementation

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

  1. arr ← [1, 2, 4, 4, 4, 7, 9], target ← 4, result ← -1

    1use strict;2use warnings;
    values this step[1, 2, 4, 4, 4, 7, 9]arr4target-1result

  2. hi ← 2, mid ← 3, result ← 3

    8while ($lo <= $hi) {9	my $mid = int($lo + ($hi - $lo) / 2);10	if ($arr[$mid] == $target) {
    values this step6 → 2hi3mid3result0lo

  3. lo ← 2, mid ← 1

    8while ($lo <= $hi) {9	my $mid = int($lo + ($hi - $lo) / 2);10	if ($arr[$mid] == $target) {
    values this step0 → 2lo1mid2hi3result

  4. hi ← 1, result ← 2, mid ← 2

    8while ($lo <= $hi) {9	my $mid = int($lo + ($hi - $lo) / 2);10	if ($arr[$mid] == $target) {
    values this step2 → 1hi3 → 2result2mid2lo

  5. stdout ← 2

    18}19print "$result\n";
    values this step2stdout2result

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.