Java 中实现的二分搜索中使用的等式和不等式运算符

Question

我一直在想为什么在Java的二进制搜索代码中，我们使用了'<='而不是简单地使用'=='。是某种优化吗？

下面这段代码来自Class：java.util.Arrays，方法：binarySearch0()

代码：

    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) { // Why here have we used '<=' rather than '=='
                    return mid;
                }

                high = mid - 1;
            }
        }

        return -(low + 1);
    }

Answer 1

您也可以使用“==”。好像midVal < key，永远不会去else部分。

Answer 2

您的代码与 JDK (http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/file/be44bff34df4/src/share/classes/java/util/Arrays.java#l1825) 中使用的代码不同，因此我只能假设您使用了某种反编译器来获得源代码。

原始源代码是可读的并且清楚地传达了意图：

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.
}

现在，如果您查看 if 语句：

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found

您可以将其重写为（仍然是与以前相同的代码）：

        if (midVal < key) {
            low = mid + 1;
        } else  {
            if (midVal > key)
                high = mid - 1;
            else
               return mid; // key found
        }

现在您可以更改第二个 if 中的比较并交换该语句的 then 和 else 分支：

        if (midVal < key) {
            low = mid + 1;
        } else  {
            if (midVal <= key) {
                return mid; // key found
            }
            high = mid - 1;
        }

此代码在功能上是等效的，但意图不再可见。

Java 中实现的二分搜索中使用的等式和不等式运算符

Equality and in-equality operators used in binary search implemented in Java

java

arrays

binary-search

data-structures