二分查找是常用的查找算法，該查找算法主要針對(duì)有序的（從大到小或從小到大排列）數(shù)組。主要有兩種方式實(shí)現(xiàn)二分查找，一種是遞歸方式，另一種是非遞歸方式
遞歸方式實(shí)現(xiàn)二分查找
/**
* 二分查找，遞歸方法
* @param nums 從小到大排列的有序數(shù)組
* @param low 左邊的索引
* @param high 右邊的索引
* @param target 要查找的目標(biāo)值
* @return 如果找到target返回target的下標(biāo)，否則返回-1
*/
publicstaticintbinarySearch(int[]nums,intlow,inthigh,inttarget){
intmid=low+(high-low)/2;//防止int溢出
//同時(shí)也可以采用位運(yùn)算>>1(相當(dāng)于除以2)更高效,
//如：int mid = low + (high - low >> 1),
//同時(shí)注意位運(yùn)算的優(yōu)先級(jí)是低于加減運(yùn)算的
if(low>high){
return-1;
? ? ?? }
if(target==nums[mid]){
returnmid;
}elseif(target>nums[mid]){//當(dāng)target大于中間數(shù)，向右遞歸
returnsearch2(nums,mid+1,high,target);
}elseif(target<nums[mid]){//當(dāng)target小于中間數(shù)，向左遞歸
returnsearch2(nums,low,mid-1,target);
}else{
return-1;
? ? ?? }
?? }
非遞歸方式實(shí)現(xiàn)二分查找
/**
* 二分查找,針對(duì)有序的數(shù)組，非遞歸方法
*
* @param nums
* @param target
* @return 返回target下標(biāo)，若target不存在則返回-1
*/
publicstaticintsearch(int[]nums,inttarget) {
intlow=0;
inthigh=nums.length-1;
while(low<=high) {
intmid=(low+high)/2;
if(target==nums[mid]) {
returnmid;
}elseif(target>nums[mid]) {
low=mid+1;
}elseif(target<nums[mid]) {
high=mid-1;
? ? ? ? ?? }
? ? ?? }
return-1;
?? }
