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.

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

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/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"

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

    16}1718arr=(4 7 1 9 3 8)
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    18arr=(4 7 1 9 3 8)19target=9
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    18arr=(4 7 1 9 3 8)19target=920result=$(linear_search "$target" "${arr[@]}")
    values this step-1result9target

  4. match ← no

    8while [ "$i" -lt "${#arr[@]}" ]; do9	if [ "${arr[i]}" -eq "$target" ]; then10		echo "$i"
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    8while [ "$i" -lt "${#arr[@]}" ]; do9	if [ "${arr[i]}" -eq "$target" ]; then10		echo "$i"
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    8while [ "$i" -lt "${#arr[@]}" ]; do9	if [ "${arr[i]}" -eq "$target" ]; then10		echo "$i"
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    8while [ "$i" -lt "${#arr[@]}" ]; do9	if [ "${arr[i]}" -eq "$target" ]; then10		echo "$i"
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    9if [ "${arr[i]}" -eq "$target" ]; then10	echo "$i"11	return
    values this step3result3i

  9. stdout ← 3

    19target=920result=$(linear_search "$target" "${arr[@]}")21echo "$result"
    values this step3stdout3result

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.