Linear Search

Linear search is the simplest searching algorithm: start at index 0 and inspect each element in order until you find a match or exhaust the array. It requires no preconditions on the data — unsorted, duplicates, mixed types — all fine.

Algorithm and Invariant

The loop invariant is: every element before index i has been checked and does not equal target. When the loop ends without returning early, the target is not present.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;   // found — return index
  }
  return -1;                           // not found
}

linearSearch([3, 7, 1, 9, 4], 9); // 3
linearSearch([3, 7, 1, 9, 4], 5); // -1

Complexity

No extra memory is allocated, so space is always O(1).

Built-in Shortcuts

JavaScript’s standard library offers two built-in linear searches:

const scores = [42, 17, 99, 55];

// indexOf — returns index or -1
scores.indexOf(99);                      // 2
scores.indexOf(0);                       // -1

// find — returns the element itself, good for objects
const users = [{ id: 1 }, { id: 2 }, { id: 3 }];
users.find((u) => u.id === 2);           // { id: 2 }

Array.indexOf uses strict equality (===). Array.find accepts a predicate, making it ideal for arrays of objects.

When Linear Beats Binary

It is tempting to reach for binary search whenever performance matters, but linear search wins in several real scenarios:

• Unsorted data — binary search requires a sorted array. Sorting costs O(n log n), which is worse than a single O(n) scan when you only search once.
• Very small n — for arrays of ten or fewer elements the overhead of maintaining lo/hi pointers and computing midpoints exceeds the cost of a simple scan. Most standard libraries switch to linear search below a certain threshold for exactly this reason.
• Linked structures — you cannot random-access the middle of a linked list in O(1), so binary search does not apply; linear scan is the only choice.
• Searching once — if you search a dataset a single time and discard it, skipping the sort and running linear search is faster overall.

Up Next

When the array is sorted you can do much better than O(n) — binary search narrows the window by half on every step.