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.

Basic Implementation

basic.pl 
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";

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.
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`.