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:
| Complexity Type | Notation | Description |
|---|---|---|
| Time Complexity | O(n) | Linear time complexity, where n is the list size. |
| Space Complexity | O(1) | Constant space complexity, regardless of list size. |
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.
