Overview
Linear Search scans the input in order and compares each item with the target. It needs no preprocessing and works on unsorted data.
FoundationSource checked
Linear Search
Finds a target by checking items one by one until a match is found or the input ends.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Beginner
- Family
- Sequential Search
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Sequential Search
Core Concepts
sequential scanequality testearly exitnot-found sentinel
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(1)
When to Use
- Use it when the input is small or unsorted.
- Use it when preprocessing or maintaining an index would cost more than the search.
- Use it as a straightforward baseline before adding a more complex lookup structure.
When Not to Use
- Avoid it for repeated searches over large static collections.
- Avoid it when sorted order or hashing can provide cheaper lookup.
What It Does
- Checks each candidate in sequence
- Returns the first matching position or a not-found result
Use Cases
- Searching small lists
- Searching unsorted data
- Using a simple baseline for correctness tests
Inputs
- Array or list
- Target value
Outputs
- Index of target
- Not-found result
Pseudocode
- 1.Start at the first item
- 2.Compare the current item with the target
- 3.Return the position if it matches
- 4.Move to the next item
- 5.Return not found if the scan ends
Canonical Example
- Input
- array = [7, 4, 9], target = 4
- Output
- index = 1
- Explanation
- The scan checks 7 first, then finds 4 at index 1.
Implementation Notes
- Define equality or matching rules before scanning.
- Return as soon as the required match is found.
- Test empty inputs and targets at the first and last positions.
Common Pitfalls
- Returning the wrong sentinel for not-found results.
- Forgetting whether the first match or all matches are required.
- Assuming linear search is harmless inside a frequently repeated loop.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow a cursor checking each item from left to right.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 5: Start at the first item
array-scanNotes
Linear search is often the right choice when simplicity beats preprocessing cost.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookAlgorithms textbook support for Linear Search's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toBinary Search
Linear search scans unsorted data, while binary search requires sorted order.
Prerequisite ofNaive String Search
Naive string search applies a direct scan-and-compare strategy over text.
Related Algorithms
Tags
SearchLinear ScanClassic