2

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

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

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

4

6 回答 6

11

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

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++;
于 2015-10-25T11:58:43.947 回答
1

使用哨兵值允许删除变量 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;
于 2015-10-25T12:15:24.867 回答
1

如果加上要搜索的值，可以在每个循环中减少一次比较，从而减少运行时间。它可能看起来像 for(i = 0;;i++) if(array[i] == elementToSearch) return i;。

于 2015-10-25T12:30:11.767 回答
1

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

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

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

于 2015-10-25T11:58:36.933 回答
1

首先，让我们将您的示例转换为使用哨兵的解决方案。

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

请注意，数组的末尾现在有一个额外的插槽来保存标记值。（如果我们不这样做，写入的行为array[length]是未指定的。）

哨兵方法的目的是减少为每个循环迭代执行的测试数量。相比：

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

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

在第一个版本中，代码对每个循环迭代都i进行了测试。array[i]在第二个版本中，i没有测试。

对于大型阵列，性能差异可能很大。

但缺点是什么？

  1. 未找到值时的结果不同；-1与length.
  2. 我们必须使数组更大以保存标记值。（如果我们做错了，我们就有可能破坏堆栈或堆上的东西。哎哟！）
  3. 数组不能是只读的。我们必须能够更新它。
  4. 如果多个线程在同一个数组中搜索不同的元素，这将不起作用。
于 2019-03-06T11:53:31.017 回答
0

关键是您可以将 for 循环转换为 while/repeat 循环。注意你是如何每次检查 i < length 的。如果你掩饰它，

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

然后你不必做额外的检查。（在这种情况下，array.length 现在大一）

于 2015-10-25T11:58:41.043 回答