linear search Algorithm
The linear search algorithm, also known as the sequential search algorithm, is a fundamental and straightforward method for searching an element in a list or an array. It works by iterating through each element in the list or array one-by-one, comparing the target value to each element until a match is found or the end of the list is reached. Linear search is considered a basic algorithm because of its simplicity and ease of implementation. It does not require any advanced data structures or pre-processing steps, making it universally applicable to any type of list or array.
However, the primary disadvantage of the linear search algorithm is its inefficiency, particularly in large datasets. The algorithm has a worst-case time complexity of O(n), meaning that its execution time increases linearly with the size of the input data. In the worst case, the target element could be the last element in the list or not present at all, requiring a full traversal of the entire list. This can be problematic when dealing with substantial amounts of data or when the search operation needs to be performed frequently. In such cases, more advanced search algorithms, such as binary search, interpolation search, or hashing techniques, are often more suitable alternatives.
"""
This is pure Python implementation of linear search algorithm
For doctests run following command:
python -m doctest -v linear_search.py
or
python3 -m doctest -v linear_search.py
For manual testing run:
python linear_search.py
"""
def linear_search(sequence, target):
"""Pure implementation of linear search algorithm in Python
:param sequence: a collection with comparable items (as sorted items not required in Linear Search)
:param target: item value to search
:return: index of found item or None if item is not found
Examples:
>>> linear_search([0, 5, 7, 10, 15], 0)
0
>>> linear_search([0, 5, 7, 10, 15], 15)
4
>>> linear_search([0, 5, 7, 10, 15], 5)
1
>>> linear_search([0, 5, 7, 10, 15], 6)
"""
for index, item in enumerate(sequence):
if item == target:
return index
return None
if __name__ == "__main__":
user_input = input("Enter numbers separated by comma:\n").strip()
sequence = [int(item) for item in user_input.split(",")]
target_input = input("Enter a single number to be found in the list:\n")
target = int(target_input)
result = linear_search(sequence, target)
if result is not None:
print(f"{target} found at position : {result}")
else:
print("Not found")
