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 index is 3.

Basic Implementation

basic.ts 
const arr: number[] = [4, 7, 1, 9, 3, 8];
const target: number = 9;
function linearSearch(arr: number[], target: number): number {
    for (let i: number = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}
const result: number = linearSearch(arr, target);
console.log(result);

Complexity

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

Implementation notes

  • TypeScript: explicit for (let i: number = 0; i < arr.length; i++). Never use arr.indexOf(target) — the lesson is teaching the walk.
  • Function signature linearSearch(arr: number[], target: number): number documents the integer-array contract.
  • The replay shows the running index, the element being checked, and a match indicator on each frame.
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`.