折半查找法又称为二分查找法,这种方法对待查找的列表有两个要求:
(1)必须采用顺序存储结构
(2)必须按关键字大小有序排列
算法思想
首先,将表的中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则查找前一子表,否则查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
例题:列表有11个元素(6,12,15,18,22,25,28,35,46,58,60),给出使用折半查找法查找12和50的过程。
//在有序表a中折半查找等于k的元素,若找到,则函数值为该元素在表中的位置
int binSearch(int a,int k)
{
low=1;
high=a.length;
while(low<=high)
{
mid=(low+high)/2;
if(k==a[mid])
return(mid);//找到待查元素
else if(k<a[mid])//未找到,则继续在前半区间查找
high=mid-1;
else//继续在后半区间查找
low=mid+1;
}
return (0);//找不到,返回0
}
java实现二分法查找