在哨兵中使用线性搜索有什么意义? [英] What's the point of using linear search with sentinel?

问题描述

我的目标是了解为什么与哨兵一起使用线性搜索比使用标准线性搜索更受欢迎.

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

维基百科提到:

另一种减少开销的方法是消除对循环索引的所有检查.这可以通过将所需项本身作为标记值插入列表的末尾来完成.

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?

推荐答案

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

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

这篇关于在哨兵中使用线性搜索有什么意义?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！