二分查找c++实现

二分查找的算法原理较为简单，在此给出c++代码实现，以及代码中遇到的问题，以及解决方案：

 # include "iostream"

 using namespace std;

 //template <class, T>

 int Binary_search( const int vector[] , int value)//采用泛型的方式

 {

     //T* low = vector[0];

     //T* high = sizeof(vetor) / sizeof(vetor)+vector[0]-1;

     int low = ;//获取最低位

     int high = sizeof(vector) / sizeof(vector[])-;//这里显示的vector

     cout << "vector:" << sizeof(vector) << endl;//这里sizeof vector等于=4，并不是4*13等于32???思考这是为什么

     cout<<";vector[0]:" << sizeof(vector[]) << endl;

     cout << "high:" << high << endl;

     //T *middle = (low + high) / 2;

     int middle;

     while (low <= high)

     {

         middle = (low + high) / ;

         if (vector[middle] > value)

         {

             high = middle - ;

         }

         if (vector[middle] < value)

         {

             low = middle + ;

         }

         if (vector[middle] == value)

         {

             return middle;

         }

     }

 }

 int main()

 {

     const int a[] = { , , , , , , , , , , , ,  };

     cout <<"a:" <<sizeof(a) << endl;

     cout<<Binary_search(a, )<<endl;

     system("pause");

     return ;

 }

其中，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）也就成了我们得到的是指针变量的大小！！！，而不是指针所指向区域的大小！！！！。这是很重要的区别。

但是二分查找明显要求我们得到查找数据的长度。那么我们该如何得到这个长度呢？

一种方法是我们在主程序中先得到数据的长度，将长度作为一个函数参数进行传递。但这种方式真的很蠢（个人觉得真的很蠢！！！，因为这样不能体现算法本身的封装性）。那么有没有其他方法呢？

如果我们采用泛型加引用的方式呢？

 # include "iostream"

 using namespace std;

 template <class T>

 int Binary_search( const T & vector ,const  T value)//采用泛型的方式

 {

     int low = ;

     int high = sizeof(vector) / sizeof(vector[])-;

     cout << "high:" << high << endl;

     int middle;

     while (low <= high)

     {

         middle = (low + high) / ;

         if (vector[middle] > value)

         {

             high = middle - ;

         }

         if (vector[middle] < value)

         {

             low = middle + ;

         }

         if (vector[middle] == value)

         {

             return middle;

         }

     }

 }

 int main()

 {

     const int a[] = { , , , , , , , , , , , ,  };

     cout <<"a:" <<sizeof(a) << endl;

     //const int value = 5;

     cout<<Binary_search(a,)<<endl;//无法执行

     system("pause");

     return ;

 }

我们的本意是：忽略传递数组的类型，采用泛型的思想设计程序，但是程序报错：

错误 1 error C2782: “int Binary_search(const T &,const T)”: 模板参数“T”不明确 c:\users\kb409\desktop\c++\binary search\binary search\binary search.cpp 34 1 Binary search

由于泛型编程掌握的并不是很好，所以并不知道这样做错在哪里，如果有大神知道，请给我留言！

最后，将代码改成了下面这个样子，程序通过：

 # include "iostream"

 using namespace std;

 template <class T>

 int Binary_search( const T & vector ,const  int value)//采用泛型的方式

 {

     int low = ;

     int high = sizeof(vector) / sizeof(vector[])-;

     cout << "high:" << high << endl;

     int middle;

     while (low <= high)

     {

         middle = (low + high) / ;

         if (vector[middle] > value)

         {

             high = middle - ;

         }

         if (vector[middle] < value)

         {

             low = middle + ;

         }

         if (vector[middle] == value)

         {

             return middle;

         }

     }

 }

 int main()

 {

     const int a[] = { , , , , , , , , , , , ,  };

     //cout <<"a:" <<sizeof(a) << endl;

     //const int value = 5;

     cout<<Binary_search(a,)<<endl;//可以执行

     system("pause");

     return ;

 }

所做的改变仅仅是将第五行const T value改变成了 int value ,鉴于目前知识水平有限吗，对模板的使用并不是很熟练，在后续中逐渐弄明白这个问题

巴特西

二分查找c++实现

最新文章

热门文章