Arrays and Iteration

Linear Search

Walk an array once looking for a target value. Return the index of the first match, or -1 if none. The simplest possible search loop.

Algorithm

Canonical input @arr = (4, 7, 1, 9, 3, 8) with $target = 9 finishes after four compares; the matching index is 3.

early exit Return the index the moment `$arr_ref->[$i]` equals the target. Walking past it would defeat the point.
sentinel return A no-match walk falls off the loop and returns `-1`.

Basic Implementation

basic.pl
Replay: real traced execution (multi-file project)
use strict; use warnings;

sub linear_search {
	my ($arr_ref, $target) = @_;
	my $i = 0;
	while ($i < scalar @$arr_ref) {
		if ($arr_ref->[$i] == $target) {
			return $i;
		}
		$i = $i + 1;
	}
	return -1;
}

my @arr = (4, 7, 1, 9, 3, 8);
my $target = 9;
my $result = linear_search(\@arr, $target);
print "$result\n";

  1. arr ← [4, 7, 1, 9, 3, 8]

    15my @arr = (4, 7, 1, 9, 3, 8);16my $target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    15my @arr = (4, 7, 1, 9, 3, 8);16my $target = 9;17my $result = linear_search(\@arr, $target);
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    16my $target = 9;17my $result = linear_search(\@arr, $target);18print "$result\n";
    values this step-1result9target

  4. match ← no

    6while ($i < scalar @$arr_ref) {7	if ($arr_ref->[$i] == $target) {8		return $i;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    6while ($i < scalar @$arr_ref) {7	if ($arr_ref->[$i] == $target) {8		return $i;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    6while ($i < scalar @$arr_ref) {7	if ($arr_ref->[$i] == $target) {8		return $i;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    6while ($i < scalar @$arr_ref) {7	if ($arr_ref->[$i] == $target) {8		return $i;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    7if ($arr_ref->[$i] == $target) {8	return $i;9}
    values this step3result3i

  9. stdout ← 3

    17my $result = linear_search(\@arr, $target);18print "$result\n";
    values this step3stdout3result

Complexity

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

Implementation notes

  • Perl: explicit while ($i < scalar @$arr_ref) with an early return $i the moment $arr_ref->[$i] == $target. Reaching for List::Util::first would hide the walk the lesson is teaching behind a CPAN-style use, and the grep operator would scan the whole array even after the match.
  • Function signature sub linear_search { my ($arr_ref, $target) = @_; ... } documents the array-reference contract (Perl passes arrays by flattening, so the reference keeps the caller's @arr intact); the -1 sentinel mirrors the language-neutral spec rather than returning undef.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.