Linear Search and When to Use It

Linear search is the one everybody dismisses. On the sizes most code actually deals with, it is frequently the fastest option and always the clearest.

The built-ins are all linear

const users = [{ id: 1, name: "Ada" }, { id: 2, name: "Grace" }]

users.find((u) => u.id === 2)       // the element, or undefined
users.findIndex((u) => u.id === 2)  // the index, or -1
users.some((u) => u.id === 2)       // true or false
users.filter((u) => u.id > 1)       // every match
;[1, 2, 3].includes(2)              // primitives only

console.log(users.length, "users to scan")

All O(n). find, findIndex and some stop at the first match; filter always walks the whole array.

Using filter(...)[0] where you meant find(...) scans the entire array to return one element. Common, and free to fix.

When linear is genuinely right

• Small arrays. Under a few hundred items, the overhead of building a Map exceeds what it saves.
• You search once. Building an index to use it a single time is pure loss.
• The condition is complex. Hash maps answer equality. "First user over 30 in Berlin" is a scan.
• Order matters. "The first match" is a scan; a Set has no useful notion of first.

Doing the arithmetic

const users = [{ id: 1 }, { id: 2 }, { id: 3 }]
const target = 2

// One lookup: scanning wins.
const found = users.find((u) => u.id === target)   // O(n), zero setup

// Many lookups: index once, then O(1) each.
const byId = new Map(users.map((u) => [u.id, u]))  // O(n) once
byId.get(target)                                    // O(1) forever after

console.log(found ? "found by scanning" : "not found")
console.log(byId.size, "entries indexed")

The rule: if lookups outnumber the cost of building the index, index. One or two lookups on a thousand items - scan. Thousands of lookups - index.

Early exit is worth more than it looks

const users = [{ isAdmin: false }, { isAdmin: true }, { isAdmin: false }]

// Walks all million even after finding a match.
const anyAdmin = users.filter((u) => u.isAdmin).length > 0

// Stops at the first one.
const anyAdmin2 = users.some((u) => u.isAdmin)

console.log(anyAdmin)   // true or false
console.log(anyAdmin2)  // the same answer, found the other way

Both are O(n) in the worst case. On real data, where the match is often early, the second is dramatically faster - Big O does not capture that, and it still matters.

The honest summary

Reach for a scan first. Move to a Map or a sort when you have a reason - repeated lookups, or a range query a scan cannot answer efficiently. Optimising a search over 50 items is time spent on nothing.