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;
    
 **二分查找的边界选取：**
    奇数二分去中间
    偶数二分取中间靠左
    但实际上，二分查找有许多变化，实现代码不同，左右边界的选取     可能会有变化，需要注意

最后

以上就是淡定灰狼为你收集整理的java二分查找方法的实现和其优化（解决整数溢出）的全部内容，希望文章能够帮你解决java二分查找方法的实现和其优化（解决整数溢出）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。