二分查找是常用的查找算法，该查找算法主要针对有序的（从大到小或从小到大排列）数组。主要有两种方式实现二分查找，一种是递归方式，另一种是非递归方式
递归方式实现二分查找
/**
* 二分查找，递归方法
* @param nums 从小到大排列的有序数组
* @param low 左边的索引
* @param high 右边的索引
* @param target 要查找的目标值
* @return 如果找到target返回target的下标，否则返回-1
*/
publicstaticintbinarySearch(int[]nums,intlow,inthigh,inttarget){
intmid=low+(high-low)/2;//防止int溢出
//同时也可以采用位运算>>1(相当于除以2)更高效,
//如：int mid = low + (high - low >> 1),
//同时注意位运算的优先级是低于加减运算的
if(low>high){
return-1;
}
if(target==nums[mid]){
returnmid;
}elseif(target>nums[mid]){//当target大于中间数，向右递归
returnsearch2(nums,mid+1,high,target);
}elseif(target<nums[mid]){//当target小于中间数，向左递归
returnsearch2(nums,low,mid-1,target);
}else{
return-1;
}
}
非递归方式实现二分查找
/**
* 二分查找,针对有序的数组，非递归方法
*
* @param nums
* @param target
* @return 返回target下标，若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;
}
