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

我的目标是理解为什么采用带有标记的线性搜索比使用标准线性搜索更受欢迎。

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

维基百科提到：

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

如果我用sentinel实现线性搜索，我必须这样做

 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

使用sentinel值允许删除变量i并相应地检查和增加变量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) { //... 

使用sentinel值可以通过以下方式重写函数

 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; 

Answer 4

如果添加要搜索的值，则可以减少每个循环中的一个比较，从而减少运行时间。 它可能看起来像（i = 0 ;; i ++）if（array [i] == elementToSearch）返回i;。

Answer 5

关键是你可以将for循环转换为while / repeat循环。 注意你每次检查i <长度。 如果你隐蔽它，

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

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