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.

Basic Implementation

basic.lua 
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)

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