折半查找--顺序表
程序员文章站
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;
}
上一篇: 企业微信通过手机号获取userid
下一篇: Java中如何取数据各个位上的值