欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-22 09:15:16
之前在牛客网上做习题发现的这个独特的顺序查询,第一次听到“监视哨”这个说法,就查了一下 具体实现就是将数组的第0位置空,在查找时将要查找的key插入作为监视哨 这样的好处是不用每次循环都检查查找是否结束,减少了元素比较次数, 最后的返回值要么是元素下标要么是数组第0位(这种情况就是到了监视哨) 以下 ......

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

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

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

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

以下是我的代码

 1 #include <iostream> 
 2 using namespace std;
 3 
 4 template<class t>
 5 int linear_search(t& arr,int key)
 6 {
 7     int length = sizeof(arr) / sizeof(arr[0]);
 8     int i = length;
 9     arr[0] = key;
10     while (arr[i] != key)
11     {
12         i--;
13     }
14     return i;
15 }
16 
17 int main()
18 {
19     int array[] = { 0, 7,9,10,11,15 };
20     int len = sizeof(array) / sizeof(array[0]);
21     cout << linear_search(array, 10);
22     return 0;
23 }

这里顺带提一下,vs2019会出现一个

error c2760: 语法错误: 意外的令牌“标识符”,预期的令牌为“;”

的错误,具体原理我不是很懂,单给出一个解决办法:

项目->属性->c/c++->语言->符合模式->否

 

最后给自己提一下醒,数组作为函数参数是传入数组首位的指针,指针是不带有数组其他属性的,

所以要在函数内获得数组的长度,只能用引用和模板的形式传入数组本身,这样就能用sizeof()获取数组长度了