linearsearch

Linear search, also known as sequential search, is a basic search algorithm that checks every element in a list in order until a target value is found or the end of the list is reached. It does not require the data to be sorted, making it simple and broadly applicable to arrays, linked lists, and strings as long as elements can be compared for equality.

The algorithm starts at the first element and compares it with the target. If a match is found, the algorithm returns the position of the match (or the element), and the search ends. If not, it proceeds to the next element, continuing until a match is found or all elements have been checked. For strings, a similar approach can be used to locate a character or substring by comparing successive elements or blocks.

Time complexity: in the worst case, every element is examined, giving O(n) time. On average, about n/2 elements are checked, which is still O(n). The best case is O(1) if the first element matches. Space complexity is O(1) auxiliary space for an iterative implementation. A recursive version uses O(n) stack space.

Advantages include simplicity and no requirement for sorting; it works on unordered data and can be used when data is frequently modified. Disadvantages include poor performance on large data sets and inefficiency compared with binary search on sorted data. It is commonly used for small collections, for simple membership tests, and as a building block in more complex search procedures.