数据结构之查找

http://www.bjfuacm.com/problem/287/

#include<iostream>
using namespace std;
#define OK 1
#define MAXSIZE 10000
typedef int Status;
typedef int ElementType;
typedef int KeyType;
typedef struct
{
    ElementType *data;
    int length;
}SqList;
Status InitList(SqList &L)
{
    L.data=new int(MAXSIZE);
    L.length=0;
    return OK;
}
int Search_Seq(SqList ST)
{
    int i;
    for(i=ST.length;ST.data[i]!=ST.data[0];i--);
    return i;
}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        SqList L;
        InitList(L);
        L.length=n;
        for(int i=1;i<=n;i++)
            cin>>L.data[i];
        cin>>L.data[0];
        if(Search_Seq(L))
            cout<<"YES"<<endl;
        else
            cout<<"NO";
    }
    return 0;
}

基于递归的折半查找
发布时间: 2017年9月18日 10:52 最后更新: 2017年9月18日 11:43 时间限制: 1000ms 内存限制: 128M

描述
请编写一个递归的折半查找算法，查找给定有序数组中的某一元素。

输入
多组数据，每组数据有三行。第一行为数组长度n，第二行为n个递增排列的数字，第三行为需要查找的数字k。当n=0时输入结束。

输出
每组数据输出一行，如果可以找到数字，则输出“YES”，否则输出“NO”。

样例输入1
5
1 4 6 7 8
6
6
1 2 5 7 9 100
8
0
样例输出1
YES
NO

#include<iostream>
using namespace std;
#define OK 1
#define MAXSIZE 10000
typedef int Status;
typedef int ElementType;
typedef int KeyType;
typedef struct
{
    ElementType *data;
    int length;
}SqList;
Status InitList(SqList &L)
{
    L.data=new int(MAXSIZE);
    L.length=0;
    return OK;
}
int Search_Seq(SqList ST)
{
    int i;
    for(i=ST.length;ST.data[i]!=ST.data[0];i--);
    return i;
}
int Search_Bin(SqList L,int low,int high)
{
    int mid=(low+high)>>1;
    if(low==high)
    {
        return 0;
    }
    else if(L.data[mid]==L.data[0])
    {
        return mid;
    }
    else
    {
        if(L.data[0]<L.data[mid])
        {
            Search_Bin(L,low,mid-1);
        }
        else
        {
            Search_Bin(L,mid+1,high);
        }
    }

}
int main()
{
    int n;
    while(cin>>n&&n!=0)
    {
        SqList L;
        InitList(L);
        L.length=n;
        for(int i=1;i<=n;i++)
            cin>>L.data[i];
        cin>>L.data[0];
        if(Search_Bin(L,1,L.length))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}