java二分查找方法的实现和其优化（解决整数溢出）
package cn.itcast.algorithm.suanFa; /** * 二分法查找实现 */ public class MainS11 { public static void main(String[] args) { int[] arr = {1,2,3,4,5,6,7,8,9,10}; int target = 2; //创建一个二分查找方法 int idx = erFen(arr,target); System.out.println(idx); } private static int erFen(int[] a, int target) { int l = 0,r = a.length-1,m; while(l < a.length){ //未优化时： // m = (l + r)/2; //方法一： // m = l + (r - l)/2; //方法二： m = (l + r) >>> 1; if (a[m] == target){ return m; }else if (a[m] > target){ r = m - 1; }else { l = m + 1; } } return -1; } }
但是在获取中间索引m的时候，
当数组里的数值太多，且求取值在右半部分时（即 m > Integer.MAX_VALUE时）会造成溢出，此时m值为负数。
解决方法如下：
**方法一：** m = (l + r)/2; 变换一下为(l/2 + r/2) --> l + (-l/2 + r/2) --> l + (r - l)/2 ==> 最后为 m = l + (r - l)/2 **方法二：** 用无符号的右移运算代替除法 相比于方法一时间的更短，效率更高 m = (l + r)/2; 变换为---> m = (l + r) >>> 1; **二分查找的边界选取：** 奇数二分去中间 偶数二分取中间靠左 但实际上，二分查找有许多变化，实现代码不同，左右边界的选取 可能会有变化，需要注意
