Arrays.binarySearch详解

Arrays.binarySearch是系统库提供的二分查找api。

先看看源代码中的注释

 /**
     * Searches the specified array of ints for the specified value using the
     * binary search algorithm.  The array must be sorted (as
     * by the {@link #sort(int[])} method) prior to making this call.  If it
     * is not sorted, the results are undefined.  If the array contains
     * multiple elements with the specified value, there is no guarantee which
     * one will be found.
 **/
1
2
3
4
5
6
7
8

这说明：该api只能用于有序递增数组（所以一般配合Arrays.sort使用），且数组中若有重复值，无法保证获得哪个值

重载“狂魔”

首先提及一下，该api提供了多个重载方法。支持八大基本类型除了boolean外（毕竟boolean数组也跟查找没多大关系），还支持Object类型和泛型，可以说是应有尽有。

此处以int类型为例说明，其它实现也大同小异

    public static int binarySearch(int[] a, int key) {
        return binarySearch0(a, 0, a.length, key);
    }
1
2
3

public static int binarySearch(int[] a, int fromIndex, int toIndex,int key) {
        rangeCheck(a.length, fromIndex, toIndex);
        return binarySearch0(a, fromIndex, toIndex, key);
    }
1
2
3
4

提供两种重载方法，若不指定起点跟终点，则默认在整个数组中查找，其中范围是 [fromIndex, toIndex),即终点是开区间

而rangeCheck则是检查提供的起点终点是否合法，直接放上源代码此处无需多解释

private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

binarySearch0方法

显然无论是提供哪种参数，最终都是交由binarySearch0方法进行处理。以下是源码

private static int binarySearch0(int[] a, int fromIndex, int toIndex,int key) {
        int low = fromIndex;
        int high = toIndex - 1; //印证上述的开区间

        while (low <= high) {  //二分查找核心代码
            int mid = (low + high) >>> 1;  //即 ÷2
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码并不复杂，return -(low + 1),则是本文讲解核心。

不同情况下的返回值

• 先说最简单的，包含该key的例子：
  对应代码中midVal==key，return mid; 不多解释。

• <数组中的某个值

1. <数组中的某个值
   相信看本文的读者都是理解二分查找的原理的，此处就不班门弄斧了。只强调一点：二分查找未命中情况下，退出循环的时候必定满足low - high =1，且low指向应插入位置，即若low=i，则[i,arr.length-1]的元素都应右移一位，最后应另arr[i]=key，
   假设arr[i-1]<key<arr[i],则 low = i

2. <数组中的全部值（其实就是特殊情况，因为数组本身就是有序递增的，＜数组中的全部值等价于＜数组首个元素）：
   循环不断重复：high=mid -1 ,至low<=high不成立。而直到循环结束low的值都没变，一直都是0

• ＞数组中的全部值
  跟<全部值正好相反，不断重复：low=mid +1 ,至low<=high不成立。而直到循环结束high的值都没变，一直都是a.length-1，而low - high = -1 ,即low= a.length 。

分析完了，现在看看源代码的注释：

 /**
     * @return index of the search key, if it is contained in the array;
     *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
     *         <i>insertion point</i> is defined as the point at which the
     *         key would be inserted into the array: the index of the first
     *         element greater than the key, or <tt>a.length</tt> if all
     *         elements in the array are less than the specified key.  Note
     *         that this guarantees that the return value will be &gt;= 0 if
     *         and only if the key is found.
     */
1
2
3
4
5
6
7
8
9
10

翻译一下这段话，意思就是：

总的来分：

• 若数组包含该key，则返回对应索引
• 否则，返回值则是 -(插入点) - 1
  插入点定义为 首个比 key 大的数组元素 的索引，
  但若不存在这样的元素，即key比数组中所有值都大，则插入点为数组长度

因此可以推导出一个结论：
只有包含该key才会返回正值，否则都是返回负值

（ps：觉不觉得插入点的定义很熟悉？
没错，源代码的return -(low + 1)，注释中的 -(插入点) - 1 转换一下，-(插入点+ 1)，所以 low就是插入点）

实例验证

• 最简单的，包含该key的例子：arr[2]=5,返回2，不多解释
• <数组中的某个值

1. <数组中的某个值
   同理，arr[1] =3 是首个比key大的值，所以插入点的值为1，计算为 -（1）-1 ，因此返回 -2

2. <数组中的全部值，套定义，arr[0]是首个比key大的值，所以插入点的值为0，计算为 -（0）-1 ，因此返回-1
   

• ＞数组中的全部值
  根据定义，插入点的值为数组长度：5，计算为 -（5）-1 ，因此返回 -6
  

如果数组为空？

这种情况自然是不属于包含key，返回正值了。
那应该是算作比全部元素小还是全部元素大呢？
答案是都一样，不要陷套了，因为是空数组：

• 若算作比全部元素小，则插入点为 0，返回 -（0）-1，即返回 -1
• 若算作比全部元素小，则插入点为数组长度：0，返回 -（0）-1，一样是返回 -1
  
  从代码层面分析：
  low = 0 ,high = 0-1=-1,直接不符合low<=high 条件，low = 0 , 插入点值为0。

拓展

正是因为这种特殊的返回值，我们平时常见的用法如下

int returnVal = Arrays.binarySearch(arr,key);
        if (returnVal < 0)
            returnVal = -(returnVal + 1);
1
2
3

<0,代表查找未命中，此时返回值为 -(low+1) ,其中low指向插入点，因此为了获得插入点，我们会另
returnVal = -(returnVal + 1) = -（-(low+1) +1）= - ( - low -1 +1) = -(-low) = low

推荐大家做一下leetCode的这道题，加深一下理解和记忆
面试题 17.08. 马戏团人塔

本文完，若有误欢迎提出。