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.rs
Replay: real traced execution (multi-file project)
fn linear_search(arr: &[i32], target: i32) -> i32 {
	for i in 0..arr.len() {
		if arr[i] == target {
			return i as i32;
		}
	}
	-1
}

fn main() {
	let arr = [4, 7, 1, 9, 3, 8];
	let target = 9;
	let result = linear_search(&arr, target);
	println!("{}", result);
}

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

    10fn main() {11	let arr = [4, 7, 1, 9, 3, 8];12	let target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    11let arr = [4, 7, 1, 9, 3, 8];12let target = 9;13let result = linear_search(&arr, target);
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    12let target = 9;13let result = linear_search(&arr, target);14println!("{}", result);
    values this step-1result9target

  4. match ← no

    2for i in 0..arr.len() {3	if arr[i] == target {4		return i as i32;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    2for i in 0..arr.len() {3	if arr[i] == target {4		return i as i32;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    2for i in 0..arr.len() {3	if arr[i] == target {4		return i as i32;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    2for i in 0..arr.len() {3	if arr[i] == target {4		return i as i32;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    3if arr[i] == target {4	return i as i32;5}
    values this step3result3i

  9. stdout ← 3

    13	let result = linear_search(&arr, target);14	println!("{}", result);15}
    values this step3stdout3result

Complexity

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

Implementation notes

  • Rust: explicit for i in 0..arr.len() with an early return i as i32 the moment arr[i] == target. The standard arr.iter().position(...) would hide the walk the lesson is teaching.
  • Function signature fn linear_search(arr: &[i32], target: i32) -> i32 documents the slice contract; the -1 sentinel mirrors the language-neutral spec rather than returning Option<usize>.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.