C++ 实现带监视哨的顺序查找算法

监视哨往往是程序里面的一个变量，如果是对数字排序的话，那么该变量一般是数值型变量。变量的赋值就相当于哨兵，当排序数列中出现与哨兵相等的值或有某种既定关系出现时，就做一种操作，比如说停止排序，或进行下一趟排序。

举例：

顺序检索的算法描述如下

				?

									int Search_Sequen(SSTable ST,KeyType key){

									//在线性表ST中顺序检索其关键字等于Key的数据元素，

									//若找到，函数值为该元素在表中的位置，否则为-1.

									ST.element[ST.length].key=key; //设置监视哨

									i=0;

									while(ST.element[i].key!=key) i++;

									if(i<ST.length)

									return i;

									else

									return -1;

									}

正文

之前在牛客网上做习题发现的这个独特的顺序查询，第一次听到“监视哨”这个说法，就查了一下

具体实现就是将数组的第0位置空，在查找时将要查找的key插入作为监视哨

这样的好处是不用每次循环都检查查找是否结束，减少了元素比较次数，

最后的返回值要么是元素下标要么是数组第0位(这种情况就是到了监视哨)

以下是我的代码

				?

									#include <iostream> 

									using namespace std;

									template<class T>

									int linear_search(T& arr,int key)

									{

									 int length = sizeof(arr) / sizeof(arr[0]);

									 int i = length;

									 arr[0] = key;

									 while (arr[i] != key)

									 {

									 i--;

									 }

									 return i;

									}

									int main()

									{

									 int array[] = { 0, 7,9,10,11,15 };

									 int len = sizeof(array) / sizeof(array[0]);

									 cout << linear_search(array, 10);

									 return 0;

									}