Buy me a coffee
Chapter 01 · Why hash tables?01 / 23

Searching a list, one by one

Your phone’s contacts app holds names and numbers. You type dave and want his number. How does it find him?

The simplest way is to start at the first entry and check each one. Is this dave? No. This one? No… dave is 9th, so that takes 9 comparisons. Searching for zoe, who isn’t there at all, means checking all 10 before you can say “not found”.

This is a linear scan, and its cost grows with the list. A million contacts means up to a million comparisons. In Big-O terms, it’s O(n).

contacts.jstested on Node 22.22.0
const contacts = [
{ name: 'carol', phone: '555-0163' },
{ name: 'alice', phone: '555-0142' },
// ...10 contacts, or 10 million
];
 
contacts.find((c) => c.name === 'dave'); // checks them one by one

Ran it on Node 22.22.0: over the lesson’s 10 contacts, finding dave took 9 comparisons and missing zoe took all 10.

Wrong, misleading or unclear? Suggest a fix