猜数游戏
问题描述:
给定一个数字,再给N个数字,要从这N个数找出这个给定的数字,最坏的情况,如果一个一个找,要猜N次才能成功。
其实我们没有必要一个一个猜,因为这些数字是有限的而且是有序的(我们给它们排个序),这是一个典型的二分搜索问题。我们可以用折半查找的策略,每次和中间的元素比较,如果比中间的元素小,那么要查找的数字就在左半部分。反之,如果比中间的元素大,那么要查找的元素就在中间元素的右边。
算法设计:
用一个一维数组s[ ]存储数据。
设变量low和high为下界和上界。
middle为搜索范围的中间变量。
x是要查找的数据。
- 初始化。设low=0。high=n-1。
- middle=(low+high)/2。即查找范围的中间元素。
- 判定low<high是否成立,成立转4,不成立,程序结束。
- 判断x与是s[middle]的关系,如果相等,那么x=s[middle],搜索成功,算法结束;如果x<s[middle],令high=middle-1; 如果x>s[middle],那么令low=middle+1,然后重复2的步骤。
详细代码:
#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)即可。