Linear Search

A search algorithm is a systematic procedure used to find a particular element or set of elements within a data structure or data set. This procedure can be implemented in many different ways, depending on the type of data structure and the specific requirements of the application.

One of the simplest and most intuitive search algorithms is the linear search, also known as sequential search.

How it works

Linear search is a search algorithm that starts at the beginning of the list and compares each element with the target value. If a match is found, the algorithm returns the index of the matching element; otherwise, it returns a value indicating that the element is not in the list.

public static int LinearSearch(int[] array, int target)
{
    var n = array.Length;

    for (var i = 0; i < n; i++)
    {
        if (array[i] == target)
        {
            return i;
        }
    }

    return -1;
}

Time Complexity

The time complexity of the linear search algorithm is determined by the number of comparisons it must perform. In the best case, the element is found on the first comparison and therefore the time complexity is O(1). In the average case, the time complexity is O(n/2). In the worst case, when the target element is not in the list or is at the end of the list, the complexity is O(n), where n is the number of elements in the list.

Space Complexity

The algorithm requires only a small constant amount of memory that is used to store the cycle counter and target value during the search process. Thus, the space complexity is O(1).

Conclusion

Linear search emerges as an easily comprehensible and implementable algorithm, suitable for locating an element within any data structure that supports sequential access, such as arrays, lists, and strings. It does not necessitate the data to be in a particular order, contributing to its versatility. However, it may not be the best fit for searching large data sets due to its inefficiency as the size of the data set escalates, causing the time complexity to increase proportionally. This also makes it unsuitable for real-time applications or scenarios necessitating swift and frequent search operations.

Despite this, more efficient search algorithms exist, including binary search and hash-based search. Nevertheless, for smaller or unordered data sets, the simplicity and ease of implementing a linear search can often outweigh its relative inefficiency, making it a potent tool in the right circumstances.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)