Java基础（39）Arrays.binarySearch方法

　　1.源码中可以看到，binarySearch方法调用了binarySearch0方法，binarySearch0方法才是标准的二分查找实现。

　　2.对于binarySearch0方法来说，注意最后的return语句return -(low + 1); // key not found.，也就是说，在没有发现要查找的key的时候，返回的是负的插入点值，所谓插入点值就是第一个比key大的元素在数组中的索引，而且这个索引是从1开始的。

例如：有数组{4,6,10,21,25,95}

分别执行下面的查询操作：

Arrays.binarySearch(b, 10); 　　 返回2  （找到了关键字，索引从0开始）

如果找不到，就从第一个数开始，索引为1，那么插入点值为4（1）,6（2）,10（3）,21（4）,25（5）,95（6）

Arrays.binarySearch(b, 2);   　　返回-1　　　4的索引是1

Arrays.binarySearch(b, 20); 　　 返回-4  　　21的索引是4

Arrays.binarySearch(b, 30); 　　 返回-6  　　95的索引是6

Arrays.binarySearch(b, 100); 　　返回-7　　　 100不在数组中，比所有元素都大，插入点值为b.length+1为7
为什么要用-(low+1)呢，因为假如用-low的话，查找2和查找4的结果都是0，这样就不对了。

　　3.调用binarySearch方法之前要先调用Arrays.sort方法对数组进行排序，否则得出的返回值不定。

    public static int binarySearch(Object[] a, Object key) {

        return binarySearch0(a, 0, a.length, key);

    }

    // Like public version, but without range checks.

    private static int binarySearch0(Object[] a, int fromIndex, int toIndex,

                                     Object key) {

        int low = fromIndex;

        int high = toIndex - 1;

        while (low <= high) {

            int mid = (low + high) >>> 1;

            @SuppressWarnings("rawtypes")

            Comparable midVal = (Comparable)a[mid];

            @SuppressWarnings("unchecked")

            int cmp = midVal.compareTo(key);

            if (cmp < 0)

                low = mid + 1;

            else if (cmp > 0)

                high = mid - 1;

            else

                return mid; // key found

        }

        return -(low + 1);  // key not found.

    }

巴特西

Java基础（39）Arrays.binarySearch方法

最新文章

热门文章