Sequential Search with Sentinel

Sentinel value is a way to improve the speed of sequential search. In traditional sequential search we need to test if the value is the key we are searching, however, in the sequential search with sentinel we put the value in the array end, therefore, the value is always found.

At the end we just need to test if the value of the 'index' variable is the last position of the array, if is that true, then, the value was not found, and the method returns -1.

Take a look at the example below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def SequentialSearch(value, array): for x in xrange(0, len(array)):   if array[x] == value:     return x return -1 def SentinelSearch(value, array): array.append(value) # Puts the value at the end of the array index = 0 while array[index] != value: # While the value is different   index += 1 array.pop() # Removes the value at the end of the array if index == len(array)-1: # If the 'index' variable is the last position of the array, returns -1   return -1 return index # Else, returns the position of the value on the array array = [1, 4, 5, 2, 42, 34, 54, 98, 89, 78, 67] print SequentialSearch(54, array) print SentinelSearch(98, array)

I hope you enjoyed it.
Any questions just comment.