Is linear search always slow?

No. It can be appropriate for small collections or searches that often match early, and requires little setup.

Can it find duplicates?

Yes, if the algorithm continues through the collection and records every match.

Why is a miss expensive?

Without extra information, the search must examine every entry before concluding that none matches.

AI Glossary / Graphs and symbolic AI / Beginner

Linear search

Definition

Linear search finds an item by checking entries one at a time until a match is found or the searchable collection is exhausted. Also called sequential search, it works without requiring the entries to be sorted. Its worst-case number of checks grows in direct proportion to the collection's size.

What it means

Suppose a list contains names, identifiers, or records. Linear search asks whether the first entry matches, then the second, and so on. A first-match search stops as soon as it succeeds. A search for all matches must continue to ensure no further match is missed.
The method is basic but useful. It requires little preparation and can work with an arbitrary matching condition, such as finding the first record whose status is overdue. The cost depends on how many entries are visited and how expensive each match check is. Simple comparison counts are not automatically elapsed-time predictions.

How it works

Begin at the first entry and evaluate the matching condition. If it succeeds, return the required result, such as the entry or its position. Otherwise advance and repeat. If no entry remains, return a clearly defined not-found result.
For n entries, a successful first-match search may need one through n checks. An unsuccessful search generally needs n checks when no additional information permits early stopping. If a unique matching entry is equally likely to occupy any position, the expected number of checks is (n + 1)/2. That average requires the stated probability assumption.

Three practical examples

A small configuration list can be scanned to find an option without building a separate index.
A program can locate the first message satisfying a custom condition, such as an unread message from a specified source.
A data-cleaning task can inspect every record to collect all entries containing a particular invalid value.

Think of it this way

Think of checking a row of labeled folders one at a time until the desired label appears. If the folder is absent, the entire row must be checked. The analogy is limited because a program's matching condition may inspect several fields or perform substantial computation, so one entry check need not have constant real-world cost.

Worked example

Consider the invented list [42, 17, 63, 17, 8], examined from left to right. Use one-based positions for this explanation.
To find the first 17, compare against 42 and then 17. The search succeeds at position 2 after two checks. It does not inspect the later 17 at position 4 because the requirement was only the first match.
To collect all occurrences of 17, inspect all five entries. The result is positions 2 and 4. Stopping after position 2 would answer a different question. To search for absent value 99, inspect all five entries and return not found.
Now consider a separate list of five distinct keys. Assume a query always requests one of those keys, with each key equally likely. The possible successful check counts are 1, 2, 3, 4, and 5, each with probability one fifth. The average is (1 + 2 + 3 + 4 + 5)/5 = 3 checks.
If instead half the queries are unsuccessful and the other half follow that uniform successful distribution, the average is 0.5 times 5 plus 0.5 times 3, or 4 checks. This illustrates why an average depends on the workload, not just the algorithm's name.
On an empty list, no entry comparisons are required and a first-match search immediately reports not found. Actual software must represent that result without confusing it with a valid first position or a stored value.

Illustrative case study

In a fictional support tool, Hazel Desk initially scans a short list of routing rules and returns the first matching rule. Later, a colleague changes the requirement to identify every applicable rule but keeps the early return after the first match.
The team adds a test case with two matching rules and discovers the mismatch. It updates the behavior to collect all matches and documents that rule order matters only for the separate first-match operation. This invented case illustrates that search correctness depends on the requested result, not merely on whether some matching record was found.

Common misconceptions and mistakes

Linear search does not require sorted data. Binary search usually does require an appropriate ordering and suitable access to positions, so replacing one with the other without checking those conditions can break correctness.
The phrase linear time describes growth in work as input size increases under the computational assumptions. It does not mean every search visits every entry, or that two lists of the same length take identical time. Also, the familiar roughly half-the-list average applies only under a suitable successful-query distribution. Frequent misses, duplicate values, or commonly requested early entries change the average.

Business use

A scan can be a sensible choice for a small collection, an infrequent query, or a condition that does not match an available index. Its simplicity can reduce implementation and maintenance overhead. For repeated lookups over large collections, evaluate whether indexing or another organization is worth its construction and update costs.
Specify first match, all matches, or mere existence before comparing designs. Measure representative queries, including misses, and count the work performed by the matching condition. If ordering is changed to improve common searches, check whether that changes which duplicate or overlapping rule is returned first.

Check your understanding

Why does finding the first 17 require two checks while finding all 17s requires five checks in the example?

Answer: The first-match task can stop at position 2. The all-matches task must inspect the remaining entries to find position 4 and confirm there are no additional matches.

Related terms

Binary search
Indexing
Predicate (logic)
Sequential search
hash table
algorithmic complexity
worst-case complexity
average-case complexity
predicate
duplicate handling

Learn next

Write down a ten-entry list with two copies of one key and count checks for first match, all matches, and a missing key. Then compare the assumptions required for binary search and hash-based lookup, including the cost of preparing and maintaining those structures.

Binary search

Sources

NIST Dictionary of Algorithms and Data Structures, linear search: https://xlinux.nist.gov/dads/HTML/linearSearch.html

Previous: Linear resolution Next: Linear search problem