猜数游戏问题描述: 给定一个数字,再给N个数字,要从这N个数找出这个给定的数字,最坏的情况,如果一个一个找,要猜N次才能成功。 其实我们没有必要一个一个猜,因为这些数字是有限的而且是有序的(我们给它们排个序),这是一个典型的二分搜索问题。我们可以用折半查找的策略,每次和中间的元素比较,如果比中间的元素小,那么要查找的数字就在左半部分。反之,如果比中间的元素大,那么要查找的元素就在中间元素的右边。 算法设计:用一个一维数组s[ ]存储数据。 设变量low和high为下界和上界。 middle为搜索范围的中间变量。 x是要查找的数据。
详细代码:#include <iostream> #include <algorithm> #include <cstdlib> #include <cstdio> using namespace std; const int M=1111111; int x; //要查找的数字 int n; //n个数字 int i; //循环 int s[M];//用来存储数字串 int BinarySearch(int n,int s[],int x) { int low=0; //确定下界 int high=n-1; //确定上界 while(low<=high) { int middle=(low high)/2; //查找的数组中的中间值 if(x==s[middle]) { return middle; //查找成功,中间值就是要查找的元素 } else if(x<s[middle]) { high=middle-1;//没有查找成功,此时知道要查找的元素在中间值的左边,所以更新上界high的位置 } else { low=middle 1; //没有查找成功,此时知道要查找的元素在中间值的右边,所以更新下界low的位置 } } return -1; } int main() { cout<<"请输入元素的个数 : " << endl; while(cin>>n) { cout << "请输入数列中的元素 :" << endl; for (i=0 ; i<n ; i ) { cin>>s[i] ; } sort(s,s n); //对存好的元素进行从小到大的排序 cout << "排序好的数组是:" << endl; for (i=0;i<n;i ) { cout << s[i] << " "; } cout << endl; cout<< "请输入要查找的元素:" << endl; cin >> x; int number=BinarySearch(n,s,x); if(number==-1) { cout << "该数组中没有要查找的元素" << endl; } else { cout << "要查找的数字在" << number 1 << "位" << endl; } } return 0; } 代码优化:可以用递归调用自己来优化这个搜索过程,那么函数中就要加入low和high两个变量。 int recursionBS(int x,int s[],int low,int high) { if(low>high) { return -1; } int middle =(high low)/2; if (x==s[middle]) { return middle; } else if (x<s[middle]) { recursionBS(x,s[],low,middle-1); } else { recursionBS(x,s[],middle 1,high); } } 接下来就只要在main函数中原来对BinarySearch(n.s.x)的调用改为 recursionBS(x,s[],0,n-1)即可。 |
|