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

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