sentinel linear search Algorithm
The Sentinel Linear Search algorithm is a variation of the Linear Search algorithm that is designed to improve its efficiency. In the traditional linear search algorithm, the search process involves iterating through the elements of a list one by one and comparing each element with the target value. The search ends when the target value is found or the end of the list is reached. This requires two comparisons in each iteration – one to check if the current element is equal to the target value, and another to check if the end of the list has been reached.
In the Sentinel Linear Search algorithm, a sentinel value is added to the end of the list, which is equal to the target value. This means that the search is guaranteed to find the target value in the list, eliminating the need for an additional comparison to check for the end of the list. As a result, the algorithm only requires a single comparison per iteration. This small modification can lead to significant time savings, particularly for large lists, as it reduces the number of comparisons by half. However, it is important to note that adding a sentinel value may not always be possible, especially in cases where the list is read-only or its size is fixed.
"""
This is pure Python implementation of sentinel linear search algorithm
For doctests run following command:
python -m doctest -v sentinel_linear_search.py
or
python3 -m doctest -v sentinel_linear_search.py
For manual testing run:
python sentinel_linear_search.py
"""
def sentinel_linear_search(sequence, target):
"""Pure implementation of sentinel linear search algorithm in Python
:param sequence: some sequence with comparable items
:param target: item value to search
:return: index of found item or None if item is not found
Examples:
>>> sentinel_linear_search([0, 5, 7, 10, 15], 0)
0
>>> sentinel_linear_search([0, 5, 7, 10, 15], 15)
4
>>> sentinel_linear_search([0, 5, 7, 10, 15], 5)
1
>>> sentinel_linear_search([0, 5, 7, 10, 15], 6)
"""
sequence.append(target)
index = 0
while sequence[index] != target:
index += 1
sequence.pop()
if index == len(sequence):
return None
return index
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 = sentinel_linear_search(sequence, target)
if result is not None:
print(f"{target} found at positions: {result}")
else:
print("Not found")
