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.cs
Replay: real traced execution (multi-file project)
using System;

class Program {
	static int LinearSearch(int[] arr, int target) {
		for (int i = 0; i < arr.Length; i++) {
			if (arr[i] == target) {
				return i;
			}
		}
		return -1;
	}

	static void Main() {
		int[] arr = new int[] { 4, 7, 1, 9, 3, 8 };
		int target = 9;
		int result = LinearSearch(arr, target);
		Console.WriteLine(result);
	}
}

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

    13static void Main() {14	int[] arr = new int[] { 4, 7, 1, 9, 3, 8 };15	int target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    14int[] arr = new int[] { 4, 7, 1, 9, 3, 8 };15int target = 9;16int result = LinearSearch(arr, target);
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    15int target = 9;16int result = LinearSearch(arr, target);17Console.WriteLine(result);
    values this step-1result9target

  4. match ← no

    5for (int i = 0; i < arr.Length; i++) {6	if (arr[i] == target) {7		return i;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    5for (int i = 0; i < arr.Length; i++) {6	if (arr[i] == target) {7		return i;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    5for (int i = 0; i < arr.Length; i++) {6	if (arr[i] == target) {7		return i;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    5for (int i = 0; i < arr.Length; i++) {6	if (arr[i] == target) {7		return i;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    6if (arr[i] == target) {7	return i;8}
    values this step3result3i

  9. stdout ← 3

    16	int result = LinearSearch(arr, target);17	Console.WriteLine(result);18}
    values this step3stdout3result

Complexity

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

Implementation notes

  • C#: explicit for (int i = 0; i < arr.Length; i++) with an early return i; the moment arr[i] == target. LINQ's Array.FindIndex(arr, x => x == target) would hide the walk the lesson is teaching.
  • Method signature static int LinearSearch(int[] arr, int target) documents the managed reference array contract; each arr[i] read is bounds-checked by the CLR, and the -1 sentinel mirrors the language-neutral spec rather than returning int?.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.