当前位置:C++技术网 > 资讯 > 输入一个数,要求用折半查找法找出该数是数组中的第几个元素

输入一个数,要求用折半查找法找出该数是数组中的第几个元素

更新时间:2016-08-22 22:53:53浏览次数:1+次

这是代码,但是我对于int main()中的表达,理解不了;还有while判断语句中的(!sign)表示的含义也不懂。麻烦了,谢谢;

#include <iostream>
using namespace std;
int main()
{
    const int n=7;
    int i,number,top,bott,mid,loca,a[n];
    bool flag=true,sign;
    char c;
    cout<<"enter data:"<<endl;
    cin>>a[0];
    i=1;
    while(i<n)
    {cin>>a[i];
    if (a[i]>=a[i-1])
    i++;
    else
    cout<<"enter this data again:";
    }
    cout<<endl;
    for(i=0;i<n;i++)
    cout<<a[i]<<" ";
    cout<<endl;
    while(flag)
    {
        cout<<"input number to look for:";
        cin>>number;
        sign=false;
        top=0;
        bott=n-1;
        if((number<a[0])||(number>a[n-1]))
        loca=-1;
        while((!sign)&&(top<=bott))
        {
            mid=(bott+top)/2;
            if(number==a[mid])
            {
                loca=mid;
                cout<<"Find"<<number<<",its position is"<<loca+1<<endl;
                sign=true;
            }
            else if(number<a[mid])
            bott=mid-1;
            else
            top=mid+1;
            
        }
        if(!sign||loca==-1)
        cout<<number<<"has not found."<<endl;
        cout<<"continu or not(Y/N)?";
        cin>>c;
        if(c==''''N''''||c==''''n'''')
        flag=false;
        
        
    }
    return 0;
}


C++技术网解答:

    通过沟通,得知你对基本上整个程序都不太清楚,不清楚的是语法。所以针对语法点在程序中的应用做一个分析。不过先将提出的:
while判断语句中的(!sign)表示的含义
    做一个解释。while(表达式)中的表达式是用来求取布尔值的,通过布尔值进行逻辑真假判断,进而决定while循环要不要继续执行。
    sign被声明为bool类型,见开始处的:
bool flag=true,sign;
    这里一次性声明了两个bool变量,flag同时还初始化了。sign没有初始化。不过在第一层while循环中被赋值为false,并作为第二层while的一个检测条件。也就是提问中的(!sign)。
    !是逻辑操作符,取反。真变成假,假变成真。所以,这里就是用来反转sign的值的。
    为什么要要令i=1 这个初值?这个问题其实很好理解。在开始时,输入了一个数据,存入了a[0]。如果i为0,那在循环中使用:
while(i<n)
{
    cin>>a[i];
    if (a[i]>=a[i-1])
        i++;
    else
        cout<<"enter this data again:";
}
    那岂不是在第二次输入的时候覆盖第一次输入的值了呢!而且,紧接着的if判断,a[i]和a[i-1]的比较,在开始只有两个数字的时候,必然是a[0]和a[1]。所以,如果i不从1开始赋值,就无法完成开始的这个比较。
    如果a[1]比a[0]大,就可以继续往后输入数字,下一组就是a[2]和a[1]的比较。第一轮循环确保得到的是依次变大的一组数字。这也就是第一个while的作用。如果换成:
while(i<n)
{
    cin>>a[i];
    if (a[i]<=a[i-1])
        i++;
    else
        cout<<"enter this data again:";
}
   那么得到的就是一组依次变小的数字,也就是降序排列数字,前者是升序排列数字。紧接的循环就是将数组依次输出。
    初始化的flag为true,所以确保可以开始进入while循环。这个循环里就是一个查找过程。因为是升序排列数字,所以输入的数字如果小于a[0](最小的数)或者大于a[n-1](最大的数)那绝对是找不到的,所以可以立刻返回。
    然后就是折半查找过程。如果找到了,就将sign设置为true,这样!sign就是false。在while判断条件中,使用&&来拼接两个判断条件,只要有一个是fasle,那么整个表达式就是false。所以,在中间找到后,立马既可以退出循环。如果没有找到,就继续折半查找。如果最后到没有找到,就提示没有找到。这都是基本的逻辑运算了,就不解释了。