Linear Search

Linear search is a straightforward and intuitive searching algorithm that finds the position of a target value within a list or array. It is also known as sequential search, and it works by checking each element in the list one by one until a match is found or the entire list has been traversed.

How Linear Search Works

Linear search is akin to the way we might search for a specific item in a list by scanning each item from the beginning until we find a match. The algorithm starts at the beginning of the list and compares the target value with each element sequentially. If a match is found, the algorithm returns the index of the matching element. If the entire list is traversed and no match is found, the algorithm typically returns a special value, such as -1, to indicate that the target value is not present in the list.

Linear Search Implementation in Python

Let’s implement a simple linear search algorithm in Python:

#implementation of linear search

def linear_search(input_list, search):
    for i in range(len(input_list)):
        if input_list[i] == search:
            return i

    return -1

given_array = [1,9,4,6,3,2,8,7]
number_to_search = 8

result = linear_search(given_array, number_to_search)
if result != -1:
    print(f"Match found. Number exist at index {result}")
else:
    print("Match Not found")

This function takes a list (arr) and a target value (target) as parameters. It iterates through each element in the list, comparing it with the target value. If a match is found, the index is returned. If the entire list is traversed without finding a match, -1 is returned.

Complexity Analysis

Time Complexity

The time complexity of linear search is O(n), where n is the number of elements in the list. This is because, in the worst-case scenario, the algorithm may need to traverse the entire list to find the target value.

Space Complexity

The space complexity of linear search is O(1), which means that the amount of additional memory used by the algorithm is constant, regardless of the size of the input list. This is because linear search only requires a small amount of memory to store variables like loop counters and the target value.

Certainly! Here’s a summary of the complexity analysis for linear search in tabular form:

This table provides a quick reference to understand the time and space complexities associated with linear search. The time complexity is linear, indicating a direct proportionality to the size of the input list. The space complexity is constant, denoting that the algorithm uses a fixed amount of additional memory, irrespective of the input size.

Conclusion

Linear search is a simple yet effective algorithm for finding a target value in a list. While it may not be the most efficient for large datasets, it is easy to understand and implement, making it suitable for small to moderately-sized lists. As you become more familiar with searching algorithms, you may explore more advanced techniques like binary search for improved efficiency in certain scenarios.

You Might Also Like:

Arrays as Data Structures Hash Tables How to Analyse an Algorithm? Linked Lists