二分法查找
wuyindengliu 2014-09-01
java二分法查找
2010-06-1818:32:48|分类：java基础|举报|字号订阅
/**
*java基本算法二分法查找
*前提int数组是升序排列
*推荐冒泡
*二分查找又称折半查找，它是一种效率较高的查找方法。
*二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的
publicclassTestBinSearch{
/**
*@paramargs
*/
publicstaticvoidmain(String[]args){
inta[]={0,1,2,3,4,5,6,7,8,9,10};
System.out.println(binSearch(a,0,a.length-1,100));
}
//二分查找递归实现
publicstaticintbinSearch(inta[],intstart,intend,intkey){
intmid=(end-start)/2+start;
if(a[mid]==key){
returnmid;
}
if(start>=end){
return-1;
}elseif(key>a[mid]){
returnbinSearch(a,mid+1,end,key);
}elseif(key<a[mid]){
returnbinSearch(a,start,mid-1,key);
}
return-1;
}
//二分查找普通循环实现
publicstaticintbinSearch(inta[],intkey){
intmid=a.length/2;
if(key==a[mid]){
returnmid;
}
intstart=0;
intend=a.length-1;
while(start<=end){
mid=(end-start)/2+start;
if(key<a[mid]){
end=mid-1;
}elseif(key>a[mid]){
start=mid+1;
}else{
returnmid;
}
}
return-1;
}
}
