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.

Basic Implementation

basic.R

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 = "")

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.

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`.