Sentinel Search is a searching algorithm for a list of items that are stored in a sequential manner. In this tutorial, we will study how the algorithm works, we will compare it to the linear search, and we will use the algorithm to see if it works.
Pre-Requisite: Linear Search
Before we move on to sentinel search, we need to understand why it exists, and to do that we need to first understand linear search.
In linear search, we go through each item of the list linearly and compare it to the target, and finally, we either find the required item or we don’t.
In this process, we make two comparisons in every iteration. The first comparison is if the list is over or not, and the second one is if the current item matches the target or not. But what if there was a way to cut down these comparisons to make the searching faster? That’s what sentinel search intends to do.
What is Sentinel Search?
Sentinel search, similar to linear search, is a sequential search algorithm. Meaning that we compare each item of the list one by one. But this algorithm is faster than linear search because it cuts down on the number of comparisons we have to do.
In sentinel search, we first insert the target at the end of the list, and then we compare each item of the list until we find the required item. Either the required item is in the list, in which case it will be found before we reach the end of the list. Or the list didn’t have the target, so the algorithm will reach the end of the list and find the target item that we have inserted.
Here, we only need to check if the item matches the target, and we don’t need to check if the list is empty. This is because we are going to find the target one way or the other and break out of the loop.
Finally, we can check if the item we found was already there or was added by us. This check will happen only once and the entire runtime of the algorithm will be cut down significantly because we have one less comparison to do in every iteration of the loop.
Implementing Sentinel Search in Python
Let us see sentinel search written in python:
def sentinel(lst, target):
size = len(lst)
lst.append(target)
i = 0
while(lst[i] != target):
i += 1
if(i == size):
return None
else:
return i
In the above code, we are starting with getting the size of the list, and then we append the target at the end of the list.
After that, we start a while-loop that will check if the current item is the same as the target or not. Since we have put the target at the end, the loop will definitely end.
In the end, we check if it ended at the last element or not. If yes, then the target isn’t present in the list, otherwise, it is. And we return the appropriate value accordingly.
The Output
Let us try to run the code and see how it works:
Conclusion
In this tutorial, we saw what sentinel search is, why we use it, how it differs from linear search, its implementation in python, and finally its output.
Hope you had a great time learning and see you in the next tutorial.