Linear search and when it is the right answer

Linear search walks the collection and compares each element. O(n) time, O(1) space, no preconditions at all.

function indexOf(items, target) {
  for (let i = 0; i < items.length; i++) {
    if (items[i] === target) return i;
  }
  return -1;
}

Dismissing it is a mistake. It is the right choice more often than beginners expect.

When linear search wins

• The data is unsorted and you will search it once. Sorting to enable binary search costs O(n log n) — more than the O(n) scan you were avoiding.
• The collection is small. For a few dozen elements, cache-friendly sequential access beats the branching of binary search on real hardware.
• You need every match, not the first. That is a full scan by definition.
• The predicate is complex. Binary search needs an ordering; "first user whose name contains 'ali' and is active" has none.

The break-even

One binary search saves you n − log₂ n comparisons but requires sorted data. So:

If you search a list more than a couple of times, the real answer is usually neither: build a Map or Set and get O(1) lookups.

Sentinel search, and why you probably should not

A classic micro-optimisation appends the target to the end so the loop needs no bounds check. It halves the comparisons per iteration and is still O(n) — and it mutates the input, which costs more in bugs than it saves in nanoseconds. Know it exists; reach for a better algorithm instead.

The interview version

"Find the first element satisfying a predicate" is linear search. Say the complexity, note that sorting first would only pay off across repeated queries, and move on. Spending time optimising an O(n) scan when the caller runs it once is exactly the judgement being assessed.