分治法——二分搜索BinarySearch

猜数游戏 

问题描述:

给定一个数字,再给N个数字,要从这N个数找出这个给定的数字,最坏的情况,如果一个一个找,要猜N次才能成功。

分治法——二分搜索BinarySearch

 其实我们没有必要一个一个猜,因为这些数字是有限的而且是有序的(我们给它们排个序),这是一个典型的二分搜索问题。我们可以用折半查找的策略,每次和中间的元素比较,如果比中间的元素小,那么要查找的数字就在左半部分。反之,如果比中间的元素大,那么要查找的元素就在中间元素的右边。

分治法——二分搜索BinarySearch

 算法设计:

用一个一维数组s[ ]存储数据。

设变量low和high为下界和上界。

middle为搜索范围的中间变量。

x是要查找的数据。

  1. 初始化。设low=0。high=n-1。
  2. middle=(low+high)/2。即查找范围的中间元素。
  3. 判定low<high是否成立,成立转4,不成立,程序结束。
  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)即可。

分治法——二分搜索BinarySearch 

 

上一篇:算法第二章上机实践报告


下一篇:Java实现Excel导入数据库,数据库中的数据导入到Excel