StringMash.com

Linear search visualizer

Watch it check each item in turn until it finds the one you want.

20 characters
Updates as you type

The animation is below

Show the steps
  1. Position 1: 4. Not 23, so move on.
  2. Position 2: 8. Not 23, so move on.
  3. Position 3: 15. Not 23, so move on.
  4. Position 4: 16. Not 23, so move on.
  5. Position 5: 23. That's 23. Found.
  6. Found 23 at position 5, after 5 checks.

Watch it sort

  • Being compared
  • Just moved
  • In its final place
  • Not being worked on

Type a list above to see it sorted step by step.

Using the visualizer

Type a list in the box and what to look for in Look for. The result says where it was found, or that it isn't there, and the animation below checks the list one item at a time. Show the steps lists every check. Words match whatever their capitals and accents, so cafe finds Café.

How linear search works

Start at the first item. If it's the one you want, stop. If not, move to the next, and keep going until you find it or run out of list. That's all there is to it.

It works on any list, in any order. The cost is time: on a list of n items it can take n checks, and on average about half that when the item is there. Binary search is far faster, but only on a list that's sorted.

A worked example

Look for 7 in 31, 7, 19, 42, 7, 3. Position 1 is 31, not 7, so move on. Position 2 is 7. Found, after 2 checks. The second 7, at position 5, is never reached: linear search stops at the first match.

Look for 10 in the same list and every check fails: 31, 7, 19, 42, 7, 3. Only after the sixth does the search know 10 isn't there. That's the worst case, and it's the same whether the missing item would have been small or large, because the list isn't in order.

How many checks it takes

ItemsLinear search, worst caseLinear search, average when the item is thereBinary search, worst case
10105.54
10010050.57
1,0001,000500.510
1,000,0001,000,000500,000.520

Where the average comes from

If the item is equally likely to be in any of the n places, finding it takes 1 check, or 2, or 3, and so on up to n, each as likely as the others. The average of 1 to n is (n + 1) ÷ 2, so about half the list. When the item isn't there, it's always n.

The binary search column assumes the list is already sorted. Sorting it first costs far more than one linear search, which is why a single look through an unsorted list is still done the linear way.

Questions

When is linear search the right choice?

When the list is short, unsorted, or searched only once. Sorting it first just to use binary search costs more than one straight look through.

What if the item is in the list more than once?

The search stops at the first one and gives its position. To find every copy, keep going to the end of the list instead of stopping, which always takes n checks.

Is it the same as sequential search?

Yes, they're two names for the same thing.

Why does the animation only go up to 3 steps a second?

Each step recolors a bar or two. The web's accessibility guidelines allow anything that flashes three flashes a second at most, and capping the animation at three steps a second keeps it well inside that. Step forward goes as fast as you can click.

Sources

Added . Last updated and reviewed . What's new