Implementing Sentinel Search in Python

Don’t miss the chance of Java programs examples with output pdf free download as it is very essential for all beginners to experienced programmers for cracking the interviews.

Sentinel Search:

Sentinel Linear Search, as the name implies, is a form of Linear Search in which the number of comparisons is decreased as compared to a standard linear search. When a linear search is conducted on an array of size N, a complete of N comparisons are made when the element to be searched is compared to all or any the elements of the array and (N + 1) comparisons are made for the index of the element to be compared in order that the index isn’t out of bounds of the array, which can be decreased in a Sentinel Linear Search.

In this search, the last element of the array is replaced with the element to be searched, and then the linear search is performed on the array without checking if the current index is inside the array’s index range or not, since the element to be searched would almost certainly be found within the array even though it was not present in the original array since the last element was replaced with i. As a result, the index to be tested will never be beyond the array’s limits. In the worst-case scenario, the number of comparisons would be (N + 2).

Examples:

Input:

given_elements =[2, 7, 3, 4, 9, 15]   key= 9

Output:

Element 9 is found at index 4

Implementing Sentinel Search in Python

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

1)Algorithm

We will begin by determining the length of the list, and then append the goal at the end.

Following that, we begin a while-loop to determine whether or not the current item is the same as the target. Since we placed the target at the end, the loop will undoubtedly come to an end.

Finally, we search to see if it ended at the last part or not. If yes, the goal is not in the list otherwise, it is. And then we return the required value.

2)Implementation:

Below is the implementation of linear search:

# function which return index if element is present else return -1
def sentinelSearch(given_list, key):
    # getting the last element of the list
    lastelement = given_list[-1]

    # the key which should  be searched is kept at the end of the last index.
    given_list[-1] = key
    i = 0

    while (given_list[i] != key):
        i += 1

    # Put the last element back
    given_list[-1] = lastelement
    # getting length of list
    length = len(given_list)
    if ((i < length - 1) or (given_list[length - 1] == key)):
        return i
    else:
        return -1


# given_list
given_list = [2, 7, 3, 4, 9, 15]

# given key
key = 9
# passing the given_list and key to sentinelSearch function
res = sentinelSearch(given_list, key)
# if result is equal to -1 then element is not present in list
if(res == -1):
    print("Given element(key) is not found in list")
else:
    print("Element", key, "is found at index", res)

Output:

Element 9 is found at index 4

3)Time Complexity

The while loop performs only one comparison per iteration and is guaranteed to terminate since the last element of the list is the search element itself. So, in the worst-case scenario (if the search factor does not exist in the list), there would be no more than N+2 comparisons ( N comparisons in the while loop and 2 comparisons in the if condition). This is superior to the ( 2N+1 ) comparisons used in Simple Linear Search.
It should be noted that both algorithms have a time complexity of O(n).
Related Programs: