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 0-indexed position is 3.

Basic Implementation

basic.sh 
#!/usr/bin/env bash
set -euo pipefail
linear_search() {
	local target=$1
	shift
	local arr=("$@")
	local i=0
	while [ "$i" -lt "${#arr[@]}" ]; do
		if [ "${arr[i]}" -eq "$target" ]; then
			echo "$i"
			return
		fi
		i=$((i + 1))
	done
	echo -1
}

arr=(4 7 1 9 3 8)
target=9
result=$(linear_search "$target" "${arr[@]}")
echo "$result"

Complexity

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

Implementation notes

  • Bash: explicit while [ "$i" -lt "${#arr[@]}" ] with an early echo "$i"; return the moment arr[i] -eq target. The shell has no built-in index_of for arrays; piping to grep -n would promote the integers to text and require parsing the line number back out of the match.
  • The function signature linear_search() { local target=$1; shift; local arr=("$@"); ... } documents the array contract by passing the target first and using shift plus "$@" to receive the array tail; 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. Bash arrays are 0-indexed, so the match position prints as 3 like the python-dsa / lua-dsa / perl-dsa 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 echoes `-1`.