C++二分法在数组中查找关键字的方法
本文实例讲述了C++二分法在数组中查找关键字的方法。分享给大家供大家参考。具体如下：
/*
此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现。
*/
#include<iostream>
usingnamespacestd;
/*
功能：实现数组的二分法查找(只算法只适合按从小到大排列的数组)
返回值：关键字在数组中的下标,返回-1表示未找到
a[]:要搜索的数组
len:数组元素个数
key:要查找的关键字
*/
intbinSearch(inta[],intlen,intkey)
{
inti=len/2;
intii=0;
if(len<1)
return-1;
if((key>a[i])&&(len-i>0))
{
ii=binSearch(a+i+1,len-i-1,key);//在后半段数组中查找
if(ii!=-1)
returnii+i+1;//加上数组前半段的长度
else
return-1;
}
elseif(key<a[i]&&i>0)//在前半段数组中查找
returnbinSearch(a,i,key);
elseif(key==a[i])
returni;//返回关键字在数组中的下标
else
return-1;//未在数组中找到关键字
}
intmain()
{
inta[]={2,4,5,20,24,35,66,78,98};
intlen=sizeof(a)/sizeof(int);
inti,key=-1;
while(1)
{
cin>>key;
i=binSearch(a,len,key);
printf("%d\n",i);
if(key>100)
break;
}
return0;
}
希望本文所述对大家的C++程序设计有所帮助。