If the algorithm reaches the end of the list, the search terminates unsuccessfully.
[1] Given a list L of n elements with values or records L0 .... Ln−1, and target value T, the following subroutine uses linear search to find the index of the target T in L.[3] The basic algorithm above makes two comparisons per iteration: one to check if Li equals T, and the other to check if i still points to a valid index of the list.
By adding an extra record Ln 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 performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end.
Should the content of the list change frequently, repeated re-organization may be more trouble than it is worth.
On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches.