What's the point of using linear search with s

问题:

My goal is to understand why adopting linear search with sentinel is preferred than using a standard linear search.

#include <stdio.h>

int linearSearch(int array[], int length) {
    int elementToSearch;
    printf("Insert the element to be searched: ");
    scanf("%d", &elementToSearch);

    for (int i = 0; i < length; i++) {
        if (array[i] == elementToSearch) {
            return i; // I found the position of the element requested
        }
    }
    return -1; // The element to be searched is not in the array
}

int main() {
    int myArray[] = {2, 4, 9, 2, 9, 10};
    int myArrayLength = 6;
    linearSearch(myArray, myArrayLength);
    return 0;
}

Wikipedia mentions:

Another way to reduce the overhead is to eliminate all checking of the loop index. This can be done by inserting the desired item itself as a sentinel value at the far end of the list.

If I implement linear search with sentinel, I have to

array[length + 1] = elementToSearch;

Though, the loop stops checking the elements of the array once the element to be searched is found. What's the point of using linear search with sentinel?

回答1:

A standard linear search would go through all the elements checking the array index every time to check when it has reached the last element. Like the way your code does.

for (int i = 0; i < length; i++) {
    if (array[i] == elementToSearch) {
        return i; // I found the position of the element requested
    }
}

But, the idea is sentinel search is to keep the element to be searched in the end, and to skip the array index searching, this will reduce one comparison in each iteration.

while(a[i] != element)
    i++;

回答2:

If you append the value to search for at the end of the array, when instead of using a for loop with initialization, condition and increment you can a simpler loop like

while (array[i++] != ementToSearch)
    ;

Then the loop condition is the check for the value you search for, which means less code to execute inside the loop.

回答3:

Using the sentinel value allows to remove variable i and correspondingly its checking and increasing.

In your linear search the loop looks the following way

for (int i = 0; i < length; i++) {
    if (array[i] == elementToSearch) {
        return i; // I found the position of the element requested
    }
}

So variable i is introduced, initialized, compared in each iteration of the loop, increased and used to calculate the next element in the array.

Also the function has in fact three parameters if to pass to the function the searched value

int linearSearch(int array[], int length, int value) {
//...

Using the sentinel value the function can be rewritten the following way

int * linearSearch( int array[], int value ) 
{
    while ( *array != value ) ++array;

    return array;
}

And inside the caller you can check whether the array has the value the following way

int *target = linearSearch( array, value );

int index = target == array + size - 1 ? -1 : target - array; 

回答4:

If you add the value to search for, you can reduce one comparison in every loop, so that the running time is reduced. It may look like for(i = 0;;i++) if(array[i] == elementToSearch) return i;.

回答5:

The point is that you can convert the for loop into a while/repeat loop. Notice how you are checking i < length each time. If you covert it,

do {
} while (array[i++] != elementToSearch);

Then you don't have to do that extra checking. (in this case, array.length is now one bigger)

回答6:

First, lets turn your example into a solution that uses sentinels.

#include <stdio.h>

int linearSearch(int array[], int length, int elementToSearch) {
    int i = 0;
    array[length] = elementToSearch;
    while (array[i] != elementToSearch) {
        i++;
    }
    return i;
}

int main() {
    int myArray[] = {2, 4, 9, 2, 9, 10, -1};
    int myArrayLength = 6;
    int mySearch = 9;
    printf("result is %d\n", linearSearch(myArray, myArrayLength, mySearch));
    return 0;
}

Notice that the array now has an extra slot at the end to hold the sentinel value. (If we don't do that, the behavior of writing to array[length] is unspecified.)

---

The purpose of the sentinel approach is to reduce the number of tests performed for each loop iteration. Compare:

    // Original
    for (int i = 0; i < length; i++) {
        if (array[i] == elementToSearch) {
            return i; 
        }
    }
    return -1;

    // New 
    while (array[i] != elementToSearch) {
        i++;
    }
    return i;

In the first version, the code is testing both i and array[i] for each loop iteration. In the second version, i is not tested.

For a large array, the performance difference could be significant.

But what are the downsides?

1. The result when the value is not found is different; -1 versus length.
2. We have to make the array bigger to hold the sentinel value. (And if we don't get it right we risk clobbering something on the stack or heap. Ouch!)
3. The array cannot be read-only. We have to be able to update it.
4. This won't work if multiple threads are searching the same array for different elements.