二分法查找

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;

}

}

相关推荐