首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Arrays 的二分查找

Arrays 的二分查找

作者头像
码农UP2U
发布2020-08-26 14:36:33
4050
发布2020-08-26 14:36:33
举报
文章被收录于专栏:码农UP2U码农UP2U

  二分查找也称为折半查找,是对有序元素查找的一种算法,在查找的过程中,不断的将搜索长度减半,因此效率不错。Java 的 JDK 提供了二分法查找的算法,使用的方法是Arrays.binarySearch()。binarySearch() 方法提供了多种数据类型的二分查找,比如实现了int、float、double、char、byte 和 Object 类型,还提供了对泛型的支持。在 JavaAPI 手册中提供了接口说明,比如如下方法:

static int binarySearch(long[] a, int fromIndex, int toIndex, long key)
static int binarySearch(long[] a, long key)
static int binarySearch(Object[] a, int fromIndex, int toIndex, Object key)
static int binarySearch(Object[] a, Object key)
static int binarySearch(short[] a, int fromIndex, int toIndex, short key)
static int binarySearch(short[] a, short key)
static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

  以上是 Arrays 类中提供的部分关于 binanrySearch() 方法的定义,对于不同类型来说,基本提供了两种方法,第一种方法需要在调用时提供数组、开始下标、结束下标和查找的值,比如:

static int binarySearch(long[] a, int fromIndex, int toIndex, long key)

  另外一种查找的方法是提供数组和查找的值即可,比如:

static int binarySearch(long[] a, long key)

  对于这两种搜索方法,在 Java 中提供了统一的调用方法,可以查看其代码,在 Java 的安装目录下找到 src.zip 文件,该文件是 Java 的部分源码。将 src.zip 文件解压缩,在java/util/Arrays.java 中可以找到以上两个方法的实现,代码如下:

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

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

  从代码中可以看到,两个方法最后都调用了 binarySearch0() 方法,但是在第二个binarySearch() 方法中调用了 rangeCheck() 方法,该方法用于检查数组长度、开始下标和结束下标的正确性,rangeCheck() 方法的实现如下:

/**
 * Checks that {@code fromIndex} and {@code toIndex} are in
 * the range and throws an exception if they aren't.
 */
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);
    }
}

  如果调用第一个 binarySearch() 方法,数组长度、开始下标和结束下标是方法中自行获取的,因此不需要进行 rangeCheck(),而调用第二个 binarySearch() 方法时,数组长度、开始下标和结束下标是调用时外部提供的,因此为了保证正确性进行了 rangeCheck()。

  二分法真正的实现是 binarySearch0() 方法,根据不同的数据类型,binarySearch0() 方法也提供了多种重载,这里只看 long 类型的实现,代码如下:

private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                 long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long 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.
}

  二分查找的思路是从有序(从小到大)数组的中间位置开始查找,如果中间位置的数小于查找的目标值,则查找数组中间值右侧的部分,如果中间位置的数大于查找的目标值,则查找数组中间值左侧的部分,如果相等,则返回当前的下标,如果没有找到则返回一个负数。

  除了上面的实现外,还有一种针对泛型的 binarySeach() 的方法,如下:

static <T> int binarySearch(T[] a, int fromIndex, int toIndex, T key, Comparator<? super T> c)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

  在上面两个方法的定义中,最后一个参数是一个比较器,比较器的作用是比较两个元素的大小用的,查看以上两个方法的实现,代码如下:

public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
    return binarySearch0(a, 0, a.length, key, c);
}

public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
                                   T key, Comparator<? super T> c) {
    rangeCheck(a.length, fromIndex, toIndex);
    return binarySearch0(a, fromIndex, toIndex, key, c);
}

  以上两个方法同样调用了 binarySearch0() 方法,该 binarySearch0() 方法的实现代码如下:

private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
                                     T key, Comparator<? super T> c) {
    if (c == null) {
        return binarySearch0(a, fromIndex, toIndex, key);
    }
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        T midVal = a[mid];
        int cmp = c.compare(midVal, 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.
}

  观察代码的第 12 行,c 是比较器,该比较器中提供了一个 compare() 方法用来比较两个元素的大小,如果 midVal 比 key 小,compare 返回负数,如果 midVal 比 key 大,compare 返回整数,如果 midVal 和 key 相等,compare 则返回 0。

  以上就是在学习 Arrays 工具类的使用时,顺便简单的阅读了它的实现,而刚好又能看懂,所以记录在此!

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-10-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 码农UP2U 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档