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

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

维基百科提到:

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.

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

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

但是，sentinel search的思路是把要查找的元素保留在最后，跳过数组下标的查找，这样会减少每次迭代中的一次比较。

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