二分查找的算法原理较为简单，在此给出c++代码实现，以及代码中遇到的问题，以及解决方案：
1 # include "iostream" 2 using namespace std; 3 4 //template <class, T> 5 int Binary_search( const int vector[] , int value)//采用泛型的方式 6 { 7 //T* low = vector[0]; 8 //T* high = sizeof(vetor) / sizeof(vetor)+vector[0]-1; 9 int low = 0;//获取最低位 10 int high = sizeof(vector) / sizeof(vector[0])-1;//这里显示的vector 11 cout << "vector:" << sizeof(vector) << endl;//这里sizeof vector等于=4，并不是4*13等于32???思考这是为什么 12 cout<<";vector[0]:" << sizeof(vector[0]) << endl; 13 cout << "high:" << high << endl; 14 //T *middle = (low + high) / 2; 15 int middle; 16 while (low <= high) 17 { 18 middle = (low + high) / 2; 19 if (vector[middle] > value) 20 { 21 high = middle - 1; 22 } 23 if (vector[middle] < value) 24 { 25 low = middle + 1; 26 } 27 if (vector[middle] == value) 28 { 29 return middle; 30 } 31 } 32 } 33 int main() 34 { 35 const int a[] = { 1, 2, 5, 8, 13, 19, 25, 38, 40, 47, 69, 48, 90 }; 36 cout <<"a:" <<sizeof(a) << endl; 37 cout<<Binary_search(a, 5)<<endl; 38 system("pause"); 39 return 0; 40 }
其中，while(){}代码段实现了二分查找的原理，但程序的运行结果并不正确。
我们知道通过 :sizeof(a)/sizeof(a[0])可以得到数组a的长度，但是经过参数传递，我们以为sizeof（vector）/sizeof(vector[0]) == sizeof(a)/sizeof(a[0])!!!但实际上，这是错误的！！！。数组不等于指针！！！。数组a传递给 vector，我们以为的是：将数组a的内容复制到数组vector，但实际的处理过程是：vector仅仅是一个指针，指向了数组a这块区域，但我们并不能通过这个指针vector来获得这块区域的大小。而sizeof（vector）也就成了我们得到的是指针变量的大小！！！，而不是指针所指向区域的大小！！！！。这是很重要的区别。
但是二分查找明显要求我们得到查找数据的长度。那么我们该如何得到这个长度呢？
一种方法是我们在主程序中先得到数据的长度，将长度作为一个函数参数进行传递。但这种方式真的很蠢（个人觉得真的很蠢！！！，因为这样不能体现算法本身的封装性）。那么有没有其他方法呢？
如果我们采用泛型加引用的方式呢？
1 # include "iostream" 2 using namespace std; 3 4 template <class T> 5 int Binary_search( const T & vector ,const T value)//采用泛型的方式 6 { 7 int low = 0; 8 int high = sizeof(vector) / sizeof(vector[0])-1; 9 cout << "high:" << high << endl; 10 int middle; 11 while (low <= high) 12 { 13 middle = (low + high) / 2; 14 if (vector[middle] > value) 15 { 16 high = middle - 1; 17 } 18 if (vector[middle] < value) 19 { 20 low = middle + 1; 21 } 22 if (vector[middle] == value) 23 { 24 return middle; 25 } 26 } 27 28 } 29 int main() 30 { 31 const int a[] = { 1, 2, 5, 8, 13, 19, 25, 38, 40, 47, 69, 48, 90 }; 32 cout <<"a:" <<sizeof(a) << endl; 33 //const int value = 5; 34 cout<<Binary_search(a,5)<<endl;//无法执行 35 system("pause"); 36 return 0; 37 }
我们的本意是：忽略传递数组的类型，采用泛型的思想设计程序，但是程序报错：
错误 1 error C2782: “int Binary_search(const T &,const T)”: 模板 参数“T”不明确 c:userskb409desktopc++binary searchbinary searchbinary search.cpp 34 1 Binary search
由于泛型编程掌握的并不是很好，所以并不知道这样做错在哪里，如果有大神知道，请给我留言！
最后，将代码改成了下面这个样子，程序通过：
1 # include "iostream" 2 using namespace std; 3 4 template <class T> 5 int Binary_search( const T & vector ,const int value)//采用泛型的方式 6 { 7 int low = 0; 8 int high = sizeof(vector) / sizeof(vector[0])-1; 9 cout << "high:" << high << endl; 10 int middle; 11 while (low <= high) 12 { 13 middle = (low + high) / 2; 14 if (vector[middle] > value) 15 { 16 high = middle - 1; 17 } 18 if (vector[middle] < value) 19 { 20 low = middle + 1; 21 } 22 if (vector[middle] == value) 23 { 24 return middle; 25 } 26 } 27 28 } 29 int main() 30 { 31 const int a[] = { 1, 2, 5, 8, 13, 19, 25, 38, 40, 47, 69, 48, 90 }; 32 //cout <<"a:" <<sizeof(a) << endl; 33 //const int value = 5; 34 cout<<Binary_search(a,90)<<endl;//可以执行 35 system("pause"); 36 return 0; 37 }
所做的改变仅仅是将第五行const T value改变成了 int value ,鉴于目前知识水平有限吗，对模板的使用并不是很熟练，在后续中逐渐弄明白这个问题
原文链接: https://www.cnblogs.com/shaonianpi/p/10416386.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/290238
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
