Linear Search, also known as Sequential Search, is a straightforward and easy-to-understand search algorithm that works well for small and unordered datasets. However it might be inefficient for larger datasets.

Steps of Linear Search

1. Initialization: Set the start of the list as the current position.
2. Comparison/Match: Compare the current element to the target. If they match, you’ve found your element.
3. Iteration: Move to the next element in the list and repeat the Comparison/Match step. If no match is found and there are no more elements, the search concludes.

Complexity Analysis

• Time Complexity: $O(n)$ In the worst-case scenario, when the target element is either the last element or not in the array, the algorithm will make $n$ comparisons, where $n$ is the length of the array.

• Space Complexity: $O(1)$ Uses constant extra space

Code Example: Linear Search

Here is the Python code:

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i  # Found, return index
    return -1  # Not found, return -1

# Example usage
my_list = [4, 2, 6, 8, 10, 1]
target_value = 8
result_index = linear_search(my_list, target_value)
print(f"Target value found at index: {result_index}")

Practical Applications

1. One-time search: When you’re searching just once, more complex algorithms like binary search might be overkill because of their setup needs.
2. Memory efficiency: Without the need for extra data structures, linear search is a fit for environments with memory limitations.
3. Small datasets: For limited data, a linear search is often speedy enough. Even for sorted data, it might outpace more advanced search methods.
4. Dynamic unsorted data: For datasets that are continuously updated and unsorted, maintaining order for other search methods can be counterproductive.
5. Database queries: In real-world databases, an SQL query lacking the right index may resort to linear search, emphasizing the importance of proper indexing.