java二分查找方法的实现和其优化（解决整数溢出）

159 阅读 0 评论 105 点赞

我是靠谱客的博主淡定灰狼，这篇文章主要介绍java二分查找方法的实现和其优化（解决整数溢出），现在分享给大家，希望可以做个参考。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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值为负数。
解决方法如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
**方法一：**
    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;
    
 **二分查找的边界选取：**
    奇数二分去中间
    偶数二分取中间靠左
    但实际上，二分查找有许多变化，实现代码不同，左右边界的选取     可能会有变化，需要注意