Java 二分查找法

青旅半醒 2022-02-09 11:45 383阅读 0赞

### 什么是二分查找？ ###

**二分查找(binary search)**,也称对数搜索(logarithmic search)，是一种在 有序数组 中查找某一特定元素的搜索算法。

*  搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
 *  如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
 *  如果在某一步骤数组为空，则代表找不到。
 *  这种搜索算法每一次比较都使搜索范围缩小一半。

--------------------

**下面是二分查找的程序代码**

public static int binary(int[] arr, int data) {
        
            int min = 0;
            int max = arr.length - 1;
            int mid;
            while (min <= max) {
        
                mid = (min + max) / 2;
                if (arr[mid] > data) {
        
                    max = mid - 1;
                } else if (arr[mid] < data) {
        
                    min = mid + 1;
                } else {
        
                    return mid;
                }
            }
            return -1;
        }

分析以上代码是否存在问题？哪里会出现 bug ？

对于上面的方法而言，问题出在第 6 行代码处：

mid = (min + max) / 2;

在 min 和 max 很大的时候，会出现溢出的情况，从而导致数组访问出错。

**改进办法：将加法变成减法，代码如下：**

public static int binary(int[] arr, int data) {
        
            int min = 0;
            int max = arr.length - 1;
            int mid;
            while (min <= max) {
        
                // 防止溢出
                mid =  min + (max - min) / 2;
                if (arr[mid] > data) {
        
                    max = mid - 1;
                } else if (arr[mid] < data) {
        
                    min = mid + 1;
                } else {
        
                    return mid;
                }
            }
            return -1;
        }

**官方的二分搜索法的实现写法：使用 位运算，代码如下：**

public static int binary(int[] arr, int data) {
        
            int min = 0;
            int max = arr.length - 1;
            int mid;
            while (min <= max) {
        
                // 无符号位运算符的优先级较低，先括起来
                mid =  min + ((max - min) >>> 1);
                if (arr[mid] > data) {
        
                    max = mid - 1;
                } else if (arr[mid] < data) {
        
                    min = mid + 1;
                } else {
        
                    return mid;
                }
            }
            return -1;
        }