二进制搜索适用于整数数组，但不适用于双精度数组

Question

我正在研究 Daniel Liang 的 Java 教科书第 10 版简介中的示例之一。我运行在第 7 章中对一维数组执行二进制搜索时遇到了一个问题。当我在整数数组上使用它时，我的代码工作正常，但当我输入双精度时它不起作用。

更新：2020 年 4 月 25 日 1:20pm 美国东部时间

我更新了代码以反映方法签名中的双数组和双键。我还包括一个方法调用。我通过引入

尝试了近似解

static boolean equals(double a, double b){
        if (Math.abs(a - b) <= epsilon) return true;
        return false;

然后在二分查找方法中调用如下：

while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (equals(key, a[mid]))
                return mid;
            else
                low= mid + 1;

我不确定这个问题是否正在失去精度，因为即使我使用的是双精度数，它们都是整数。下面是教科书方法签名中的原始代码，已更改为反映双重。

class Scratch {

//I created two class array variables here to test the binary search approach. 

static double[] myList = {12.0,34.0,5.0,6.0,78.0,89.0,0.0};
static int[] a = {5,1,3,3,4};

//Main method call 
public static void main(String[] args) {
      System.out.println(binarySearch(myList, 12.0));


    }
public static int binarySearch(double[] a, double key){
        int low = 0;
        int high = a.length-1;
        while(high>=low){
            int mid = (int) ((low+high)/2);
            if (key < a[mid])
                high = mid - 1;
            else if (key == a[mid])
                return mid;
            else
                low= mid + 1;
        }
        return -low -1;
    }

计算机正在打印一个负数，表示未找到密钥。

谢谢！

Answer 1

double 是一个精确的数字吗？

比较双精度数和整数时，十进制值的变化会使比较语句为假。

解决方法是在比较时将 double 转换为 int。

public class Main {
    public static void main(String[] args) throws Exception {
        double d1 = 100.000000001;
        double d2 = 100.000000000;
        int i = 100;

        System.out.println(d1 == i);
        System.out.println(d2 == i);
        int int1 = (int)d1;
        int int2 = (int)d2;

        System.out.println(int1 == i);
        System.out.println(int2 == i);
    }
}

输出：

false
true
true
true

Answer 2

你没有给我们足够的信息来确定你是如何出现故障的，但我猜你做了这样的事情：

double[] a = ...     // create and initialize
int i = ...          // a valid subscript for 
int result = binarySearch(a, (int)(a[i])); 
                     // result is -1

这就是它不起作用的原因。

将浮点值转换为整数类型时，可能会降低精度；即 1.5 变为 1 并且您丢失了 0.5.
当您使用==、<、>等比较浮点类型和整数类型时，整数值将转换为浮点数中最接近的值点类型 ... 在比较数字之前。这种转换也可能会降低精度。

因此，当我们查看您的代码在做什么时，您将在 a 数组中使用 double，将其转换为 int，以便您可以使用它作为 key ... 然后每次 binarySearch 进行比较时将 key 转换回 double。

double -> int -> double.

您看到故障的原因是初始 double 和最终 double 对于您正在搜索的 a[i] 不同。所以 == 在您希望 true.

时给您 false

解决方案是将 key 的类型更改为与您正在搜索的数组的基本类型相同。这样就不需要转换或转换值了。

Ulilop 在他的回答中提出了另一个相关的观点。即使我们排除我上面描述的转换，计算机浮点数和算术上的浮点数从根本上来说是不精确的。例如：

double one_third = 1.0 / 3.0;
double one = one_third * 3.0;
System.printf(one == 1.0);       // prints "false" !!!!

因此，无论何时进行任何涉及浮点值比较的操作，都需要考虑计算中出现舍入误差的可能性。

有关此主题的更多信息，请阅读以下内容：

Why are floating point numbers inaccurate?
Is floating point math broken?

您终于向我们提供了您的真实代码。

您的真实代码给出错误答案的原因是您在无序数组中执行二进制搜索。二进制搜索仅在您要搜索的数组已排序时才有效。正如 Wikipedia 所述：

"In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array."

Answer 3

正如其他人所提到的，double 类型具有精度 limit。

您可能会考虑更改此行 else if (key == a[mid])。

而不是制定严格的 ==，您可以尝试引入 "good enough" 标准。例如

// it can really be any number. depending on how "precise" you want
static double epsilon = 1e-9; 
static boolean equals(double a, double b) {
    if (Math.abs(a-b) <= epsilon) return true; 
    return false; 
}
... 
...
else if (equals(key, a[mid])) return mid; 
...

编辑：为了让二分查找算法起作用，数组必须是SORTED。二分查找背后的关键思想 Divid and Conquer。

它背后的想法很直接：对于一个大问题，如果我们能降低解决它的复杂性，那么它就变成了一个小问题。（第 1 步）如果我们能以某种方式将较小的问题简化为更小的问题（可能通过重新应用第 1 步中的技术），则离找到解决方案（第 2 步）更近了一步。在每一步中，我们都越来越接近，直到问题变得微不足道。

推荐在网上看一些不错的视频，比如这个one

二进制搜索适用于整数数组，但不适用于双精度数组

Binary search works for integer arrays, but not for double arrays

java

binary-search

计算机正在打印一个负数，表示未找到密钥。