二分查找的实现代码JAVA

一、思路

1.前提: 有已排序数组A (假设已经做好)
2.定义左边界L、 右边界R,确定搜索范围，循环执行二分查找(3、4两步)
3.获取中间索引 M = Floor((L+R) 1/2)
4.中间素索引的值 A[M] 与待搜索的值T进行比较
①A[M]==T 表示找到，返回中间索引
②A[M]>T, 中间值右侧的其它元素都大于T,无需比较，中间索引左边去找，M- 1设置为右边界，重新查找
③A[M]<T, 中间值左侧的其它元素都小于T,无需比较，中间索引右边去找，M+ 1设置为左边界，重新查找
5.当L>R时， 表示没有找到，应结束循环

二、实现代码（普通版）

public class BinarySearch {public static void main(String[] args){int[] array = {1,5,8,11,19,22,31,35,40,45,48,49,50};int target=48;int idx=binarySearch(array,target);System.out.println(idx);}//二分查找，找到返回目标值下标，没找到返回-1;public static int binarySearch(int[] a,int target){int L=0;int R=a.length-1;int M;while (L<=R){M=(L+R)/2;if(a[M]==target)return M;else if(a[M]>target)R=M-1;else if(a[M]<target)L=M+1;}return -1;}
}

三、整数溢出问题

问题：上述代码中如果

int L=0;
int R=Integer.MAX_VALUE-1;

那么在第二次二分时将出现M超过int的取值范围，导致上溢出。

解决方法：
①通过等价运算解决

m=(r+l)/2==>l/2+r/2==>l+(-l/2+r/2)==>l+(r-l)/2;

②通过移位计算除法，无符号右移（因为下标非负）

m=(r+l)/2==>（l+r)>>>1

四、改进代码

public class BinarySearch {public static void main(String[] args){int[] array = {1,5,8,11,19,22,31,35,40,45,48,49,50};int target=48;int idx=binarySearch(array,target);System.out.println(idx);}//二分查找，找到返回目标值下标，没找到返回-1;public static int binarySearch(int[] a,int target){int L=0;int R=a.length-1;int M;while (L<=R){//改进代码，无符号右移计算除法M=(L+R)>>>1;if(a[M]==target)return M;else if(a[M]>target)R=M-1;else if(a[M]<target)L=M+1;}return -1;}
}