Lecture
Linear, sequential search — is an algorithm for finding a given value of an arbitrary function on a certain interval. This algorithm is the simplest search algorithm and, unlike, for example, binary search, it imposes no restrictions on the function and has the simplest implementation. The search for the function's value is carried out by simply comparing the next value under consideration (as a rule, the search proceeds from left to right, that is, from smaller argument values to larger ones), and if the values match (to one degree of precision or another), the search is considered complete.
If the interval has length N, then a solution can be found to within 
in time 
. Thus, the asymptotic complexity of the algorithm is — 
. Due to its low efficiency compared to other algorithms, linear search is usually used only when the search interval contains very few elements; nevertheless, linear search requires no additional memory or processing/analysis of the function, so it can operate in streaming mode with data received directly from any source. Likewise, linear search is often used in the form of linear algorithms for finding a maximum/minimum.
As an example, one can consider searching for the value of a function on the set of integers, represented in tabular form.
The variables 
and 
contain, respectively, the left and right boundaries of the array segment where the element we need is located. The examination begins with the first element of the segment. If the sought value is not equal to the value of the function at this point, a transition is made to the next point. That is, as a result of each check, the search area decreases by one element.
int function LinearSearch (Array A, int L, int R, int Key);
begin
for X = L to R do
if A[X] = Key then
return X
return -1; // element not found
end;
For a list of n elements, the best case is one in which the sought value is equal to the first element of the list and only one comparison is required. The worst case occurs when the value is not in the list at all (or it is located at the very end of the list), in which case n comparisons are needed.
If the sought value occurs in the list k times and all occurrences are equally likely, then the expected number of comparisons
For example, if the sought value occurs in the list once, and all occurrences are equally likely, then the average number of comparisons equals 
. However, if it is known that it occurs once, then n — 1 comparisons suffice, and the average number of comparisons will equal
(for n = 2 this number equals 1, which corresponds to a single if-then-else construct).
In any case, the computational complexity of the algorithm is O(n).
Linear search is usually very simple to implement and applicable if the list contains few elements, or in the case of a single search in an unordered list.
If it is anticipated that the same list will be searched a large number of times, it often makes sense to preprocess the list, for example by sorting it and subsequently using binary search, or by building some efficient data structure for searching. Frequent modification of the list can also affect the choice of further actions, since it makes it necessary to rebuild the structure.
Comments