VietMX Staff asked 3 years ago
The idea behind linear search is to compare the search item with the elements in the list one by one (using a loop) and stop as soon as we get the first copy of the search element in the list. Now considering the worst case in which the search element does not exist in the list of size N then the Simple Linear Search will take a total of 2N+1 comparisons (N comparisons against every element in the search list and N+1 comparisons to test against the end of the loop condition).
for (int i = 0; i < length; i++) { // N+1 comparisons
if (array[i] == elementToSearch) { // N comparisons
return i; // I found the position of the element requested
}
}The idea of Sentinel Linear Search is to reduce the number of comparisons required to find an element in a list. Here we replace the last element of the list with the search element itself and run a while loop to see if there exists any copy of the search element in the list and quit the loop as soon as we find the search element. This will reduce one comparison in each iteration.
while(a[i] != element) // N+2 comparisons worst case
i++;In that case the while loop makes only one comparison in each iteration and it is sure that it will terminate since the last element of the list is the search element itself. So in the worst case ( if the search element does not exists in the list ) then there will be at most N+2 comparisons (N comparisons in the while loop and 2 comparisons in the if condition). Which is better than (2N+1) comparisons as found in Simple Linear Search.
Take note that both the algorithms (Simple Linear and Sentinel) have time complexity of O(n).
/// <summary>
/// Gets the index of first founded item
/// </summary>
/// <typeparam name="T">The type of array</typeparam>
/// <param name="array">Input array</param>
/// <param name="value">Value of searching item</param>
/// <param name="equalityComparer">Custom comparer</param>
/// <returns>The index of founded item or -1 if not found</returns>
public static int BetterLinearSearch < T > (this IEnumerable < T > array, T value, IEqualityComparer < T > equalityComparer = null) {
if (equalityComparer == null) equalityComparer = new DefaultEqualityComparer < T > ();
int arrayLength = array.Count();
T lastItem = array.Last();
array = array.SetElement(arrayLength - 1, value);
int index = 0;
while (!equalityComparer.Equals(array.ElementAt(index), value))
index++;
if (index < arrayLength - 1) return index;
if (equalityComparer.Equals(lastItem, value)) return arrayLength - 1;
return - 1;
}