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.

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.

Basic Implementation

basic.js
Replay: real traced execution (multi-file project)
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);

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

    1const arr = [4, 7, 1, 9, 3, 8];2const target = 9;
    values this step[4, 7, 1, 9, 3, 8]arr

  2. target ← 9

    1const arr = [4, 7, 1, 9, 3, 8];2const target = 9;3function linearSearch(arr, target) {
    values this step9target[4, 7, 1, 9, 3, 8]arr

  3. result ← -1

    10}11const result = linearSearch(arr, target);12console.log(result);
    values this step-1result9target

  4. match ← no

    4for (let i = 0; i < arr.length; i++) {5    if (arr[i] === target) {6        return i;
    values this stepnomatch0i4arr[i]9target

  5. match ← no

    4for (let i = 0; i < arr.length; i++) {5    if (arr[i] === target) {6        return i;
    values this stepnomatch1i7arr[i]9target

  6. match ← no

    4for (let i = 0; i < arr.length; i++) {5    if (arr[i] === target) {6        return i;
    values this stepnomatch2i1arr[i]9target

  7. match ← yes

    4for (let i = 0; i < arr.length; i++) {5    if (arr[i] === target) {6        return i;
    values this stepyesmatch3i9arr[i]9target

  8. result ← 3

    5if (arr[i] === target) {6    return i;7}
    values this step3result3i

  9. stdout ← 3

    11const result = linearSearch(arr, target);12console.log(result);
    values this step3stdout3result

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.