vizlearn
Home / Algorithms

Linear Search

Algorithms & Data StructuresBy Updated

The most fundamental search algorithm: checking every element in a sequence until the target is found or the end is reached.

Parameters

12

Visualization

Step: 0
Enter a target and click Step to start searching.

Algorithm Insight

Linear search examines each element in an array one by one in sequential order.

  • 1. Start from the first element (index 0).
  • 2. Compare current element with the Target.
  • 3. If they match, search is successful!
  • 4. Otherwise, move to the next element and repeat.

Efficiency

Time Complexity O(N)
Space Complexity O(1)

Overview

Linear search scans values from one end until it finds the target or reaches the end. It works on unsorted data without preprocessing, making it useful for small inputs or one-off searches; a missing target requires checking every element.

Check each item in order

For [42, 17, 8, 91, 5], searching for 91 checks four values and returns index 3. Searching for 100 checks all five and reports no match.

Use Search Target to choose a value and Array Size to change the input. Press Randomize Array, then Next Step or Auto-Run to follow the comparisons.

Cost

The best case is one comparison when the first item matches. The worst case is n comparisons when the target is last or absent, so time is O(n) and extra space is O(1). If a successful target is equally likely to be at any of n positions, the average is (n + 1)/2 comparisons.

Linear search is a good fit when data is unsorted, small, or checked only once. If the data is sorted and many searches are needed, binary search reduces each search to O(log n) comparisons, though the data must remain sorted. If many repeated membership checks use hashable keys, a set or dictionary can provide average constant-time lookup after construction.

Common mistakes with Linear Search

  • Stopping after a mismatch: continue until the target is found or the input ends.
  • Returning the wrong duplicate: a left-to-right scan returns the first matching index.
  • **Using -1 without checking:** valid Python negative indices make it easy to accidentally read the last element when a search failed.
  • Ignoring sortedness trade-offs: sorting solely to run one search may cost more than scanning.

Sources and next steps

Run it in Python

Three searches through the same ten-item list — one that hits immediately, one that has to walk the whole way, and one for a value that is not there at all. The last line counts the average rather than asserting it.

linear_search.pyPython 3
Output
How the code works
  1. for i, value in enumerate(a):The entire algorithm is this loop. There is no precondition to check and no structure to maintain, which is why linear search works on anything you can iterate.
  2. if value == target: return iReturning inside the loop is what makes the best case O(1). A version that records the index and keeps going would always cost n.
  3. return -1Reached only after every item failed. A miss always costs the full n — the worst case and the not-found case are the same case.
  4. comparisons = [data.index(x) + 1 for x in data]For each value, how many comparisons finding it took. Averaged, this lands on (n + 1) / 2: half the list, which is where the usual “half the array on average” figure comes from.
Change one thing
  • Move 2 to the front of data. The average does not change — you made one search cheaper and nine dearer.
  • Search for a value in a list of one million: replace data with list(range(1_000_000)) and comment out the print inside the loop. Then compare that with binary search on the same list.
  • Change the loop to for value in a: and return True/False. That is what Python's in operator does on a list, and it is why x in big_list is slow while x in big_set is not.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set Array Size to its maximum (25). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Linear search needs the data to be:
  2. The program prints an average of comparisons over every value in the list. What does it land on?
  3. Which case costs the full n comparisons?





 Cheat sheet
Linear Search
Step through an array one element at a time and see exactly when brute-force scanning is genuinely the right choice.
ALGORITHMS · vizlearn.in/dsa/linear_search.html
More in Algorithms
AlgorithmsBinary SearchAlgorithmsInterpolation SearchAlgorithmsFibonacci SearchAlgorithmsBubble Sort
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact