cf.completefrontend
SEARCHING & BINARY SEARCH · FOUNDATION

Linear search

Check the items one by one, from the first to the last, until you find the one you want.

Time O(n)Space O(1)3 practice problemsStep-through picture

The idea

Linear search is the simplest way to find something in a list. You look at the first item. If it is not the one you want, you look at the second item, then the third, and so on. You stop as soon as you find a match, or when you run out of items.

It works on any list, sorted or not. It needs no setup and no extra memory. The cost is time: in a list of 1,000 items, you may need to look at all 1,000 before you can say "not found".

For small lists, or lists you search only once, linear search is often the best choice. Sorting a list first just to search it once takes longer than one plain pass.

An everyday example

Looking for your keys in a row of drawers

You know your keys are in one of the drawers of a long cabinet, but not which one. The drawers are in no special order. So you open the first drawer and look. Not there. You close it and open the next one. You keep going until you see the keys. If you reach the last drawer and still have no keys, they are not in the cabinet.

How the example maps to the code
In the exampleIn the code
The row of drawersThe array items
Opening the next draweri++ in the loop
"Are my keys in this drawer?"items[i] === target
Finding the keys and stoppingreturn i
Reaching the end with no keysreturn -1

From the slow way to linear search

  1. Imagine a list you know nothing about: it isn't sorted, there is no index, and there are no hints. The question is "is target in here, and where?". Any item you skip could be the one you want, so you can't honestly answer "no" until you have looked at every item.
  2. So the only real choice is the order in which you look. Going from index 0 upward is the simplest order, and it gives a bonus for free: the first match you meet is the first match in the list, which is what most callers want.
  3. You also want to stop as early as you can. Once items[i] === target is true, nothing after i can change the answer, so returning right away saves work. If the target sits near the front, you finish after a few checks, even in a huge list.
  4. Last, you need a clear answer for "not there". If the counter gets past the last index with no match, every item has been ruled out, so return a value that can't be an index, like -1. A counter i from 0 to items.length - 1, one check, an early return, and -1 after the loop: that loop is linear search.

How it works

  1. Start with i = 0, the index of the first item.
  2. Look at items[i] and compare it with target.
  3. If they are equal, stop and return i.
  4. If not, add 1 to i and look at the next item.
  5. If i reaches items.length, every item was checked and none matched, so return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function linearSearch(items, target) {
  2. for (let i = 0; i < items.length; i++) {
  3. if (items[i] === target) {
  4. return i;
  5. }
  6. }
  7. return -1;
  8. }

How fast it is

TimeO(n)
Extra memoryO(1)

In the worst case the loop looks at each of the n items once. It only stores the index i, so the memory does not grow with the list.

  • Best caseO(1)

    The target is items[0], so the first check returns 0.

  • Average caseO(n)

    The target is at a random position: about n / 2 checks on average. Halving doesn't change the Big-O, so it is still O(n).

  • Worst caseO(n)

    The target is the last item or is missing: all n items are checked, a million checks for a million items.

Common mistakes

  • Using <= in the loop, as in i <= items.length. The last step reads items[items.length], which is undefined. Use <.
  • Returning -1 inside the loop when the first item does not match. The search stops after one check. Only return -1 after the loop ends.
  • Using == instead of ===, so "0", 0, and false count as matches of each other. Use === unless you really want loose matching.
  • Running a linear search inside another loop over a big list, which makes O(n²) work. If you search the same list many times, build a Set or Map once, or sort it and use binary search.

When to use it

Look for these clues in a problem:

  • The list is not sorted, and you only need to search it once or a few times.
  • The list is small, say a few dozen items, so a plain loop is fast enough.
  • You need the first item that matches a rule, not an exact value, such as the first price over 100.
  • Each item must be checked anyway, for example to count matches or find the smallest value.

Check yourself

Answer each one in your head first, then open it.

If a list has 1,000 items and the target is missing, how many comparisons does linear search make?

Exactly 1,000, one per item. It can't stop sooner, because any unchecked item might be the target.

Why doesn't items.indexOf(NaN) find a NaN in the list?

indexOf compares with ===, and NaN === NaN is false. items.includes(NaN) uses a different rule, called same-value-zero, and returns true.

Why is calling includes inside a loop over the same list a problem?

Each includes is a linear search, so n calls cost about n × n checks, which is O(n²). Building a Set once makes each check about one step.

When can linear search beat binary search, even on sorted data?

When the list is tiny, say a few dozen items, or the target is almost always near the front. The plain loop does very little work per step, and binary search's advantage only shows on bigger lists.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule, true at the top of every loop: none of the items before index i equals target. At the start i is 0, so there are no items before it, and the rule is true with nothing to check.

Each step keeps the rule. The loop only reaches i++ when items[i] === target was false, so after i grows by one, the item just passed is known not to match either. When the check is true, the function returns i, and because of the rule, no earlier index matched: this is the first match.

The loop always ends, because i grows by one each time and stops at items.length. When it stops there, the rule says none of the items from 0 to items.length - 1 match. That is every item in the list, so -1 is the right answer.

Going deeper

3 more ideas

Why it never misses the target

The loop looks at every index from 0 up to items.length - 1, in order, and it only stops early when it finds a match. So if the loop finishes without a match, every single item was checked, and the target really is not in the list. Because it walks from the start, the match it returns is always the first one.

How long it takes

If the list has n items, the worst case checks all n of them. That is written O(n): the time grows in step with the list's size. Twice as many items means up to twice as many checks. The best case is one check, when the target is the first item.

Searching from the end, or with a rule

To find the last match, run the loop backwards from items.length - 1 down to 0. To find the first item that passes a test, replace items[i] === target with that test, such as items[i] > 100. JavaScript has these built in: indexOf, lastIndexOf, find, findIndex, and findLast all do a linear search for you.

Work it by hand

Every step in a table, with why

Look for 11 in an unsorted list of 5 numbers that doesn't contain it, so every item gets checked.

items = [21, 8, 15, 8, 30], target = 11

Stepiitems[i]items[i] === targetWhat happensWhy
1021falseNo match, so i++The loop starts at the first index. 21 is not 11.
218falseNo match, so i++8 is smaller than 11, but the list isn't sorted, so this says nothing about the items after it.
3215falseNo match, so i++15 is bigger than 11. In a sorted list we could stop here. In an unsorted list we can't.
438falseNo match, so i++A second 8. A search for 8 would have returned 1, the first copy, and never reached this one.
5430falseNo match, so i++This is the last index, items.length - 1.
65--5 < 5 is false: stopThe loop condition fails, so the loop ends without reading items[5], which would be undefined.

It returns -1 after 5 checks, one per item. That is the worst case: a missing target always costs n checks.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Linear searchO(n)O(1)The list is unsorted, small, or searched only once or twice. There is no setup cost at all.
Binary searchO(log n)O(1)The list is already sorted and searched many times. Sorting first costs O(n log n), so it only pays off after many searches.
Hash set lookupO(1)O(n)You will ask "is it there?" many times about the same list. Building the Set costs one O(n) pass, then each lookup is about one step.

Extra memory: O(1): one counter, i, whatever the list's size. A method like filter, which returns every match, builds a new array and uses O(n) space instead.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Linear search and the other approaches, on a scale where each line up is 10 times more steps.
  • Linear search O(n)
  • Binary search O(log n)
  • Hash set lookup O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Linear search101,0001 million
Binary search31020
Hash set lookup111

Inputs that need care

5 tricky inputs
An empty list: items = []
i < items.length is 0 < 0, which is false at once. The loop body never runs and the function returns -1.
Duplicates: items = [4, 9, 4], target 4
It returns 0, the first copy, and never looks at index 2. To get the last copy, loop from items.length - 1 down to 0. To get all of them, collect the indexes instead of returning.
NaN as the target: items = [3, NaN]
NaN === NaN is false, so it never matches and returns -1. Test with Number.isNaN(items[i]) instead. items.includes(NaN) uses a different equality rule and returns true.
Objects: items = [{ id: 3 }], target { id: 3 }
=== compares references, not contents, so two separate objects with the same fields don't match and it returns -1. Search by a field instead, such as items[i].id === 3, which is what findIndex is for.
Mixed types: items = ["5", 5], target 5
"5" === 5 is false, so it returns 1, not 0. That strictness is usually what you want. With == it would return 0.

Variations and follow-ups

Twists interviewers add

Search with a rule

Replace items[i] === target with any test, such as items[i].price > 100. That is what find and findIndex do. The proof doesn't change: every item before the returned one failed the test, so it is the first that passes.

Search from the end

Loop i from items.length - 1 down to 0 to get the last match, as lastIndexOf and findLast do. This helps when new items are added at the end and you want the newest match.

Sentinel search

Put the target at the end of the list as a stopper. Then the loop needs only one check per item, items[i] !== target, instead of two, because it is sure to stop. After the loop, check whether it stopped at a real item or at the stopper. In JavaScript the saving is tiny and changing the input is risky, so this matters mostly in low-level code.

Move found items forward

If the same few items are searched for again and again, move each found item one step toward the front. Popular items then drift to the start and are found in a few checks. This only works when you own the list and its order doesn't matter.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when the input has no order and you only look once: "find the first item that...", "does the list contain...". Also spot it as a hidden cost: an includes or indexOf call inside a loop is a linear search, and it makes the whole thing O(n²).
  • Say the rule out loud: "every item before i has been checked and doesn't match". It explains both why you return the first match and why returning -1 after the loop is safe.
  • Test by hand: an empty list, a target at index 0, a target at the last index, and a missing target. The last two catch the <= versus < bug in the loop condition.
  • The usual follow-up is "what if we search this list many times?". Answer: build a Set, or a Map from value to index, once in O(n), and each lookup is then O(1). If you also need "nearest value" questions, sort once and use binary search.

Where frontend code uses it

The same idea in real UI code
  • Array.prototype.indexOf, includes, find, findIndex, and findLast are all linear searches. Their cost grows with the array's length.
  • document.querySelector walks the DOM tree in document order and returns the first element that matches the selector, which is a linear search over the nodes.
  • A small autocomplete list (say 50 country names) is usually filtered with a plain loop on every keystroke, because a fancier index is not worth it at that size.

Related algorithms