折半查找

#include<iostream>
using namespace std;

typedef struct {
    int key;
}ElemType;

typedef struct{
        ElemType *elem;
        int length;
}SSTable;

//判断a是否等于b
int EQ(int a,int b)
{
    if (a == b)
        return 1;
    else
        return 0;
}

//判断a是否小于b
int LT (int a,int b)
{
    if ( a < b)
        return 1;
    else 
        return 0;
}

//判断a是否小于等于b
int LQ(int a,int b)
{
    if ( a <= b)
        return 1;
    else
        return 0;
}

//静态查找表的建立
void SSTable_Creat(SSTable &ST, int n)
{
    int m = 1;
    ST.elem = (ElemType*)malloc(sizeof(ElemType)*(n));
    for ( m ; m < n+1  ; m++)
    {
        cout << "请输入第" << m  << "的数据:";
        cin >> ST.elem[m].key;
    }
    ST.length = n;
}

//无序线性表的的顺序查找
int Search_1(SSTable ST,int key)
{
    int i = 0;
    ST.elem[0].key = key;

    /*
    i = ST.length;
    while( ST.elem[i].key != key)
    {
        --i;
    }
    */

    for ( i = ST.length ; ! EQ(ST.elem[i].key,key); --i) ;  
    return i;
}

//有序表的二分法查找
int Search_2(SSTable ST,int key)
{
    int low,mid,high;
    low = 1;
    high = ST.length;
    while(low <= high)
    {
        mid = ( low + high ) / 2;
        if (EQ(key,ST.elem[mid].key))
            return mid;
        else if(LT(key,ST.elem[mid].key))
            high = mid - 1;
        else
            low = mid + 1;
    }
    return 0;
}

int main()
{
    int m,n,i,j;
    SSTable S1,S2;

    cout << "无序线性顺序表的查找" << endl;
    cout << "请输入无序线性表数据个数：";
    cin >> m;
    SSTable_Creat(S1,m);
    cout << "请输入查找的元素:" ;
    cin >> n;
    cout << Search_1(S1,n) << endl;

    cout << "有序线性顺序表的查找" << endl;
        cout << "请输入有序线性表数据个数：";
        cin >> i;
        SSTable_Creat(S2,i);
        cout << "请输入查找的元素:" ;
        cin >> j;
        cout << Search_2(S2,j) << endl;

    return 0;
}