java二分查找的原理实现

本教程操作环境：windows7系统、java10版，DELL G3电脑。

1.二分查找步骤描述

（1）首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2

（2）用待查关键字值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找

（3）对确定的缩小区域再按折半公式，重复上述步骤。

最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放。 折半查找算法举例

（1）必须采用顺序存储结构。

（2）必须按关键字大小有序排列。

3.实例

publicclassDemo{

publicstaticvoidmain(String[]args){
int[]arr={-1,0,3,5,9,12};//查找的数组
intsearchNum=13;//查找的目标数
Arrays.sort(arr);

intresultOne=binarySearchOne(arr,searchNum,0,arr.length-1);
System.out.println(resultOne);

intresultTwo=binarySearchTwo(arr,searchNum);
System.out.println(resultTwo);
}

/**
*递归实现
*@paramarr
*@paramsearchNum
*@paramstart
*@paramend
*@return
*/
publicstaticintbinarySearchOne(int[]arr,intsearchNum,intstart,intend){
if(start>end)
return-1;
intmiddle=(start+end)/2;
if(searchNum<arr[middle])
returnbinarySearchOne(arr,searchNum,start,middle-1);
elseif(searchNum>arr[middle])
returnbinarySearchOne(arr,searchNum,middle+1,end);
else
returnmiddle;
}

/**
*非递归实现
*@paramarr
*@paramsearchNum
*@return
*/
privatestaticintbinarySearchTwo(int[]arr,intsearchNum){
intstart=0;
intend=arr.length-1;
while(start<=end){
intmiddle=(start+end)/2;
if(searchNum<arr[middle])
end=middle-1;
elseif(searchNum>arr[middle])
start=middle+1;
else
returnmiddle;
}
return-1;
}
}