折半查找算法

折半查找

折半查找也称二分查找，但它要求查找表必须是顺序结构存储且表中数据元素按关键码有序。折半查找在查找成功时，所进行的关键码比较次数至多为⎡log2(n+1)⎤。平均查找长度为ASL=log2(n+1)-1，时间复杂度是O(log2n)。

折半查找的程序代码如下：

#include

#define MAXSIZE 10

typedef int DataType;

typedef struct S_T{

DataType data[MAXSIZE];

int length;

}S_T;

void CreateS_T(S_T *t){

int i;

cout

cin>>t->length;

t->data[0]='z';

for(i=1;ilength;i++)

cin>>t->data[i];

}

int Binary_Search(S_T *t,DataType kx){

int low,high,mid;

int count;

int flag;

low=1;

count=1;

high=t->length;

flag=0;

while(low

mid=(low+high)/2;

if(kxdata[mid])

high=mid-1;

else

if(kx>t->data[mid])

low=mid+1;

else{

flag=mid;

break;

}

count++;

}

cout

return flag;

}

void main(){

int i;

DataType kx;

S_T *t=new S_T;

CreateS_T(t);

cout

cin>>kx;

i=Binary_Search(t,kx);

if(i==0)

cout

else

cout