Arrays and Iteration

Linear Search

Inspect each element in order; return the first matching index, or -1 if the scan completes without a match.

Algorithm

Canonical input arr = [4, 7, 1, 9, 3, 8] with target = 9 matches at index 3 after four frames.

Basic Implementation

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

Complexity

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

Implementation notes

  • JavaScript: explicit for loop with an early return i; from a function.
  • Never call arr.indexOf(target); the lesson is teaching the loop and the early exit.
  • The replay highlights arr[i], shows whether arr[i] === target, and flips result from -1 to i on the matching frame before returning.
linear scan Visit each element in order and compare to the target.
early return Returning as soon as a match is found avoids visiting later elements.