欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半查找--顺序表

程序员文章站 2024-03-20 17:49:04
...

折半查找又称二分查找。

优点:比较次数少,查找速度快,平均性能好;
缺点:要求待查表为有序表,且插入删除困难。

因此:折半查找方法适用于不经常变动而查找频繁的有序列表。

时间复杂度:假设n个元素,时间复杂度为log2(n)。

/**在有序顺序表中进行**/
#include<iostream>
using namespace std;

#define Max 20

typedef int DataType;

typedef struct
{
    DataType *data;
    int length;
}SqList;

void InitList(SqList &L)
{
    L.data=new int[Max];
    L.length=0;
}

void CreateList(SqList &L)
{
    int a,i;
    cout<<"输入数据的个数:";
    cin>>a;
    L.length=a;
    cout<<"输入数据:";
    for(i=1;i<=L.length;i++)
        cin>>L.data[i];
}

int BS(SqList L,DataType e)//Binary search=折半查找
{
    int mid,low=1,height=L.length;
    while(low<=height)
    {
        mid=(low+height)/2;
        if(e>L.data[mid])
            low=mid+1;
        else if(e<L.data[mid])
            height=mid-1;
        else
            return mid;
    }
    return 0;//查找不到就返回0
}
int main(void)
{
    int a,b;
    SqList L;
    InitList(L);
    CreateList(L);
    cout<<"输入想要查找的数据:";
    cin>>a;
    b=BS(L,a);
    if(!b)
        cout<<"查找失败"<<endl;
    else cout<<"该数据为顺序表中第"<<b<<"个元素"<<endl;
}

折半查找--顺序表