linear search

(algorithm)

Definition: Search an array or list by checking items one at a time.

Also known as sequential search.

Generalization (I am a kind of ...)
search.

Specialization (... is a kind of me.)
transpose sequential search.

Aggregate child (... is a part of or used in me.)
move-to-front heuristic.

See also binary search, hash table.

Note: Average run time is Θ (n/2) when the item is found.

Author: PEB

Implementation

More information

expected time. Demonstration.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Thu Oct 27 10:01:17 2005.
HTML page formatted Thu Oct 27 10:13:15 2005.

Cite this as:
Paul E. Black, "linear search", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/linearSearch.html