Arrays and Iteration

Linear Search

Walk a vector 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 <- c(4, 7, 1, 9, 3, 8) with target <- 9 finishes after four compares; the matching 1-indexed position is 4.

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

arr <- c(4, 7, 1, 9, 3, 8)
target <- 9
result <- linear_search(arr, target)
cat(result, "\n", sep = "")

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

    12arr <- c(4, 7, 1, 9, 3, 8)13target <- 9
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    12arr <- c(4, 7, 1, 9, 3, 8)13target <- 914result <- linear_search(arr, target)
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    13target <- 914result <- linear_search(arr, target)15cat(result, "\n", sep = "")
    values this step-1result9target

  4. match ← no

    3while (i <= length(arr)) {4	if (arr[i] == target) {5		return(i)
    values this stepnomatch1i4arr[i]9target

  5. match ← no

    3while (i <= length(arr)) {4	if (arr[i] == target) {5		return(i)
    values this stepnomatch2i7arr[i]9target

  6. match ← no

    3while (i <= length(arr)) {4	if (arr[i] == target) {5		return(i)
    values this stepnomatch3i1arr[i]9target

  7. match ← yes

    3while (i <= length(arr)) {4	if (arr[i] == target) {5		return(i)
    values this stepyesmatch4i9arr[i]9target

  8. result ← 4

    4if (arr[i] == target) {5	return(i)6}
    values this step4result4i

  9. stdout ← 4

    14result <- linear_search(arr, target)15cat(result, "\n", sep = "")
    values this step4stdout4result

Complexity

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

Implementation notes

  • R: explicit while (i <= length(arr)) with an early return(i) the moment arr[i] == target. The stdlib which(arr == target)[1] is vectorised and would hide both the running index and the early-exit the lesson is teaching, and match(target, arr) would package the whole loop in a single C call.
  • Function signature linear_search <- function(arr, target) documents the array contract; the -1 sentinel mirrors the language-neutral spec rather than returning NA_integer_ (which R programmers often reach for, but which would re-route control flow through if (is.na(result)) ... in the caller).
  • The replay shows the running index, the element being checked, and a match indicator on each frame. R vectors are 1-indexed, so the match position prints as 4 instead of 3 like the 0-indexed language cohorts.