halfsearch.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>

const int N=8;
void output(int table[],int n);        //输出数组的n个元素,略

int halfsearch(int table[],int k)      //顺序表的折半查找算法
{                                      //查找k值,找到时返回下标,不成功时返回-1
    int left=0,right=N-1,mid;
    bool find=false;
    while(left<=right && !find)        //子序列边界有效
    {
        mid=(left+right)/2;            //子序列的中间位置
        cout<<"left="<<left<<" right="<<right<<" mid="<<mid<<" ";
        cout<<table[mid]<<"=="<<k<<"?\n";
        if(k==table[mid]) 
            find=true;                 //查找成功
        else
            if(k<table[mid])
                right=mid-1;           //子序列为原序列的前半部
            else
                left=mid+1;            //子序列为原序列的后半部
    }
    if(find)
        return mid;
    else 
        return -1;
}  

void main()
{
    int a[N]={1,4,7,10,13,16,19,22},k=13;
    cout<<"N="<<N;
    output(a,N);
    cout<<"halfsearch("<<k<<")="<<halfsearch(a,k)<<"\n";
}
/*
程序运行结果 ：
N=8  table:  1  4  7  10  13  16  19  22  
left=0 right=7 mid=3 10==13?
left=4 right=7 mid=5 16==13?
left=4 right=4 mid=4 13==13?
halfsearch(13)=4
*/

void output(int table[],int n)         //输出数组的n个元素
{
    cout<<"  table:  ";
    for(int i=0;i<n;i++)
        cout<<table[i]<<"  ";
    cout<<endl;
}


/*
bool halfsearch2(int table[],int k)     //查找k值,找到时返回1，递归?
{                                      //不成功时返回0
    int left=0,right=N-1,mid;
    bool find = false;
    while (left<=right && !find)       //子序列边界有效
    {
        mid = (left + right) / 2;      //子序列的中间位置
        cout<<"left="<<left<<" right="<<right<<" mid="<<mid<<" ";
        cout<<table[mid]<<"=="<<k<<"?\n";
        if (k==table[mid]) 
            find = true;               //查找成功
        else
            if (k<table[mid])
                right = mid - 1;       //子序列为原序列的前半部
            else
                left = mid + 1;        //子序列为原序列的后半部
    }
    return find;
}  

*/