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[$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.php
Replay: real traced execution (multi-file project)
<?php
function linear_search($arr, $target) {
	$i = 0;
	while ($i < count($arr)) {
		if ($arr[$i] == $target) {
			return $i;
		}
		$i = $i + 1;
	}
	return -1;
}

$arr = [4, 7, 1, 9, 3, 8];
$target = 9;
$result = linear_search($arr, $target);
echo $result . "\n";

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

    13$arr = [4, 7, 1, 9, 3, 8];14$target = 9;
    values this step[4, 7, 1, 9, 3, 8]$arr

  2. $target ← 9

    13$arr = [4, 7, 1, 9, 3, 8];14$target = 9;15$result = linear_search($arr, $target);
    values this step9$target[4, 7, 1, 9, 3, 8]$arr

  3. $result ← -1

    14$target = 9;15$result = linear_search($arr, $target);16echo $result . "\n";
    values this step-1$result9$target

  4. match ← no

    4while ($i < count($arr)) {5	if ($arr[$i] == $target) {6		return $i;
    values this stepnomatch0$i4$arr[$i]9$target

  5. match ← no

    4while ($i < count($arr)) {5	if ($arr[$i] == $target) {6		return $i;
    values this stepnomatch1$i7$arr[$i]9$target

  6. match ← no

    4while ($i < count($arr)) {5	if ($arr[$i] == $target) {6		return $i;
    values this stepnomatch2$i1$arr[$i]9$target

  7. match ← yes

    4while ($i < count($arr)) {5	if ($arr[$i] == $target) {6		return $i;
    values this stepyesmatch3$i9$arr[$i]9$target

  8. $result ← 3

    5if ($arr[$i] == $target) {6	return $i;7}
    values this step3$result3$i

  9. stdout ← 3

    15$result = linear_search($arr, $target);16echo $result . "\n";
    values this step3stdout3$result

Complexity

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

Implementation notes

  • PHP: explicit while ($i < count($arr)) with an early return $i; the moment $arr[$i] == $target. The stdlib array_search($target, $arr) would hide the walk the lesson is teaching and would return false rather than -1 on a miss.
  • Function signature function linear_search($arr, $target) documents the array contract; the -1 sentinel mirrors the language-neutral spec rather than returning false / null.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.