Editing Linear search (section)

{{Distinguish|Line search}}{{short description|Sequentially looking in an array}}
{{one source|date=November 2010}}

{{Infobox algorithm
|name={{PAGENAMEBASE}}|class=[[Search algorithm]]
|time=[[big O notation#Orders of common functions|''O''(''n'')]]
|space = [[big O notation#Orders of common functions|''O''(1)]] iterative
|best-time=[[big O notation#Orders of common functions|''O''(1)]]
|average-time=[[big O notation#Orders of common functions|''O''(''n'')]]
|optimal=Yes
|data=
}}

In [[computer science]], '''linear search''' or '''sequential search''' is a method for finding an element within a [[list (computing)|list]]. It sequentially checks each element of the list until a match is found or the whole list has been searched.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}

A linear search runs in [[Time complexity#Linear time|linear time]] in the [[Best, worst and average case|worst case]], and makes at most {{math|''n''}} comparisons, where {{math|''n''}} is the length of the list. If each element is equally likely to be searched, then linear search has an average case of {{math|{{Sfrac|''n+1''|2}}}} comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other [[search algorithm]]s and schemes, such as the [[binary search algorithm]] and [[hash table]]s, allow significantly faster searching for all but short lists.{{Sfn|Knuth|1998|loc=§6.2 ("Searching by Comparison Of Keys")}}