Linear Search

You've lost your friend's phone number, but you know it's somewhere in your contacts — a long, jumbled list that nobody ever sorted. How do you find it? You do the only thing that always works: you start at the top and read one name at a time — "not it… not it… not it…" — until either you spot the name you want, or you fall off the bottom of the list and admit it isn't there.

That plain, patient, check-everything method is a real algorithm with a real name: linear search. To find a value in a list, you look at each item in turn, in order, from the start:

It's called "linear" because you walk along the list in a straight line, one step after another. The huge advantage — the reason every programmer knows it — is that it makes no assumptions: the list can be sorted or a complete mess, numbers or names, and linear search still works. That is not true of the cleverer searches you'll meet later.

Watch the pointer walk the list

Here we're searching a list of numbers for the target 23. The highlighted box is the item we're checking right now; step through and watch the pointer march along until it lands on a match.

Every box before the match got a "no" — those are the comparisons we had to make. The item we wanted sat at index 4, so it took 5 checks (indices 0, 1, 2, 3, 4) to reach it. Hold on to that idea of counting comparisons — it's how we judge whether a search is fast or slow.

Linear search in code

The algorithm is a single loop over the array (see ). We visit each index in turn, compare, and the moment we find the target we return its index — which also stops the search early, because there's no point looking further. If the loop finishes without ever returning, the value was never there, and by convention we return -1 to mean "not found". Press Run and read the log of every comparison it makes:

function linearSearch(list: number[], target: number): number { for (let i = 0; i < list.length; i++) { console.log("Checking index " + i + " (value " + list[i] + ")..."); if (list[i] === target) { // is THIS the one? console.log("Found " + target + " at index " + i + "!"); return i; // stop early — we're done } } console.log(target + " is not in the list."); return -1; // fell off the end: not found } const numbers: number[] = [8, 15, 4, 16, 23, 42, 11]; linearSearch(numbers, 23); // near the middle

Notice the log stops the instant 23 is found — the numbers 42 and 11 after it are never even looked at. Try changing the target to 8 (the very first item) and then to 99 (not in the list at all), and re-run. You'll see the number of "Checking…" lines change dramatically.

It works on anything — even unsorted words

Because linear search never relies on the order of the items, it happily searches a list of strings that are in no particular order. The code is the same shape; only the types change:

function findName(names: string[], target: string): number { for (let i = 0; i < names.length; i++) { if (names[i] === target) return i; } return -1; } const pupils: string[] = ["Zoe", "Amir", "Priya", "Ben", "Lucia"]; console.log("Priya is at index", findName(pupils, "Priya")); // 2 console.log("Sam is at index", findName(pupils, "Sam")); // -1 (not here)

This list isn't alphabetical, and it doesn't matter one bit. That "works on any list" property is linear search's superpower — and, as we'll see, also its weakness.

How many comparisons? Best, worst and average

The fair way to measure the work an algorithm does is to count its key operation. For a search, that's the number of comparisons — how many items we check before we finish. For a list of n items, linear search has three cases worth knowing:

The important takeaway: the worst-case work grows in direct proportion to the size of the list. Double the list, and in the worst case you double the checks. Computer scientists write this as O(n) — "order n", or linear time. This little experiment counts the comparisons for you as the list gets bigger:

function comparisonsToFindLast(n: number): number { const list: number[] = []; for (let i = 0; i < n; i++) list.push(i); // [0, 1, 2, ..., n-1] const target = n - 1; // the LAST item = worst case let comparisons = 0; for (let i = 0; i < list.length; i++) { comparisons++; if (list[i] === target) break; } return comparisons; } for (const n of [10, 20, 40, 80]) { console.log("List of " + n + " → worst-case comparisons: " + comparisonsToFindLast(n)); }

Every time the list doubles, so does the worst-case number of checks. That's what O(n) looks like in practice.

When the item is in the list, you get to stop the moment you hit it. But to be certain something is absent, you have no shortcut — you must inspect every last element before you can honestly say "it's not here". So searching for a value that doesn't exist always costs the full n comparisons, tying with "the target is the last item" for the most expensive case.

Linear search is simple and universal, but it can be painfully slow on big lists. Searching a phone book of 1{,}000{,}000 names for someone near the end could mean up to a million comparisons. Because the cost grows with the list size, it just doesn't scale to huge data.

There's a catch, though: to go faster you usually need the list to be sorted first. If your data is in order, a much cleverer method called binary search can find any item in only about \log_2 n comparisons — roughly 20 checks for that million-name list, instead of a million. That's the trade-off to remember: linear search works on any list but is slow; binary search is blazing fast but demands a sorted list. Reach for linear search on small or unsorted data, and reach for binary search once the list is big and sorted.