Editing Linear search (section)

==Algorithm==
A linear search sequentially checks each element of the list until it finds an element that matches the target value. If the [[algorithm]] reaches the end of the list, the search terminates unsuccessfully.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search")}}

===Basic algorithm===
Given a list {{math|''L''}} of {{math|''n''}} elements with values or [[Record (computer science)|records]] {{math|''L''<sub>0</sub> .... ''L''<sub>''n''−1</sub>}}, and target value {{math|''T''}}, the following [[subroutine]] uses linear search to find the index of the target {{math|''T''}} in {{math|''L''}}.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm B"}}

# Set {{math|''i''}} to 0.
# If {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, the search terminates successfully; return {{math|''i''}}.
# Increase {{math|''i''}} by 1.
# If {{math|''i'' < ''n''}}, go to step 2. Otherwise, the search terminates unsuccessfully.

===With a sentinel===
The basic algorithm above makes two comparisons per iteration: one to check if {{math|''L''<sub>''i''</sub>}} equals ''T'', and the other to check if {{math|''i''}} still points to a valid index of the list. By adding an extra record {{math|''L''<sub>''n''</sub>}} to the list (a [[sentinel value]]) that equals the target, the second comparison can be eliminated until the end of the search, making the algorithm faster. The search will reach the sentinel if the target is not contained within the list.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm Q"}}

# Set {{math|''i''}} to 0.
# If {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, go to step 4.
# Increase {{math|''i''}} by 1 and go to step 2.
# If {{math|''i'' < ''n''}}, the search terminates successfully; return {{math|''i''}}. Else, the search terminates unsuccessfully.

===In an ordered table===
If the list is ordered such that {{math|''L''<sub>0</sub> &le; ''L''<sub>1</sub> ... &le; ''L''<sub>''n''−1</sub>}}, the search can establish the absence of the target more quickly by concluding the search once {{math|''L''<sub>''i''</sub>}} exceeds the target. This variation requires a sentinel that is greater than the target.{{Sfn|Knuth|1998|loc=§6.1 ("Sequential search"), subsection "Algorithm T"}}

# Set {{math|''i''}} to 0.
# If {{math|''L''<sub>''i''</sub> &ge; ''T''}}, go to step 4.
# Increase {{math|''i''}} by 1 and go to step 2.
# If {{math|''L''<sub>''i''</sub> {{=}} ''T''}}, the search terminates successfully; return {{math|''i''}}. Else, the search terminates unsuccessfully.