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.go 
package main

import "fmt"

func linearSearch(arr []int, target int) int {
	for i := 0; i < len(arr); i++ {
		if arr[i] == target {
			return i
		}
	}
	return -1
}

func main() {
	arr := []int{4, 7, 1, 9, 3, 8}
	target := 9
	result := linearSearch(arr, target)
	fmt.Println(result)
}

Complexity

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

Implementation notes

  • Go: explicit for i := 0; i < len(arr); i++ with an early return i the moment arr[i] == target. The standard slices.Index would hide the walk the lesson is teaching.
  • Function signature func linearSearch(arr []int, target int) int documents the integer-slice contract; the -1 sentinel mirrors the language-neutral spec.
  • 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[i]` equals the target. Walking past it would defeat the point.
sentinel return A no-match walk falls off the loop and returns `-1`.