对哨兵使用线性搜索有什么意义？

Question

我的目标是理解为什么采用带哨兵的线性搜索比使用标准的线性搜索更可取。

#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;
}

维基百科提到：

另一种降低开销的方法是消除对循环索引的所有检查。这可以通过将所需的项本身作为一个哨兵值插入到列表的远端来完成。

如果我用哨兵实现线性搜索，我必须

array[length + 1] = elementToSearch;

但是，一旦找到要搜索的元素，循环就会停止检查数组的元素。对哨兵使用线性搜索有什么意义？

Answer 1

标准的线性搜索将遍历所有元素，每次检查数组索引，以检查何时到达最后一个元素。就像你的代码一样。

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

但是，哨兵搜索的思想是最终保持要搜索的元素，并跳过数组索引搜索，--这将减少每次迭代中的一个比较。

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

Answer 2

如果在数组末尾追加要搜索的值，则可以使用更简单的循环，而不是使用具有初始化、条件和增量的for循环，例如

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

然后循环条件是对您搜索的值的检查，这意味着要在循环中执行的代码较少。

Answer 3

使用前哨值允许删除变量i，并相应地对其进行检查和增加。

在线性搜索中，循环如下所示

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

因此，变量i被引入，初始化，在循环的每一次迭代中进行比较，增加并用于计算数组中的下一个元素。

此外，如果要将搜索的值传递给函数，则该函数实际上有三个参数。

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

使用前哨值，可以通过以下方式重写该函数

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

    return array;
}

在调用方内部，您可以检查数组是否具有以下方式的值

int *target = linearSearch( array, value );

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