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 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.lua
Replay: real traced execution (multi-file project)
local function linear_search(arr, target)
	local i = 1
	while i <= #arr do
		if arr[i] == target then
			return i
		end
		i = i + 1
	end
	return -1
end

local arr = {4, 7, 1, 9, 3, 8}
local target = 9
local result = linear_search(arr, target)
print(result)

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

    12local arr = {4, 7, 1, 9, 3, 8}13local target = 9
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    12local arr = {4, 7, 1, 9, 3, 8}13local target = 914local result = linear_search(arr, target)
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    13local target = 914local result = linear_search(arr, target)15print(result)
    values this step-1result9target

  4. match ← no

    3while i <= #arr do4	if arr[i] == target then5		return i
    values this stepnomatch1i4arr[i]9target

  5. match ← no

    3while i <= #arr do4	if arr[i] == target then5		return i
    values this stepnomatch2i7arr[i]9target

  6. match ← no

    3while i <= #arr do4	if arr[i] == target then5		return i
    values this stepnomatch3i1arr[i]9target

  7. match ← yes

    3while i <= #arr do4	if arr[i] == target then5		return i
    values this stepyesmatch4i9arr[i]9target

  8. result ← 4

    4if arr[i] == target then5	return i6end
    values this step4result4i

  9. stdout ← 4

    14local result = linear_search(arr, target)15print(result)
    values this step4stdout4result

Complexity

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

Implementation notes

  • Lua: explicit while i <= #arr do with an early return i the moment arr[i] == target. There is no stdlib find for arbitrary sequences (only string.find), so the loop already documents the iteration shape the lesson is teaching, and an ipairs loop would obscure the running index.
  • Function signature local function linear_search(arr, target) documents the array contract; the -1 sentinel mirrors the language-neutral spec rather than returning nil (which Lua programmers usually reach for, but which would re-route control flow through if result == nil then ... in the caller).
  • The replay shows the running index, the element being checked, and a match indicator on each frame. The 1-based index means the match position prints as 4 instead of 3 like the 0-indexed language cohorts.