我正在研究Daniel Liang撰写的Java入门手册第10版中的示例之一。
在第7章中，对一维数组执行二进制搜索时遇到了一个问题。当我在整数数组上使用我的代码时，它可以正常工作，但是当我输入一个double时，它不能工作。
这是我用于整数数组的代码：
二进制搜索
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;
}
上面的代码对整数数组没有任何干扰，但是当我将其修改为double时，它会返回一个值，该值指示未找到键-即使当我输入数组中的键时也是如此。
这是我用于双精度数组的代码
二进制搜索
public static int binarySearch(double [] a, int 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;
}
请告知我是否需要对代码进行其他更改才能使其与double一起使用。到目前为止，这本书还没有给我提供双重示例。
您没有给我们足够的信息来知道确定您如何遇到故障，但是我想您已经做了类似的事情：
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。==，<，>等比较浮点类型和整数类型时，整数值将转换为浮点类型中最接近的值... ...在数字之前比较。此转换也可能会降低精度。因此，当我们查看您的代码在做什么时，您将在double数组中获取一个a，并将其强制转换为int，以便可以将其用作key ...然后每次key进行比较时，将double转换回binarySearch。
double -> int -> double.
您看到故障的原因是，对于要搜索的double，初始double和最终a[i]不同。因此，当您希望==成为false时，会给您true。
解决方案是将key的类型更改为与要搜索的数组的基本类型相同。这样就无需强制转换或转换值。
Ulilop在回答中提出了另一个相关的观点。即使我们排除上述转换，从根本上讲，计算机浮点数和浮点算术也不精确。因此，例如：
double one_third = 1.0 / 3.0;
double one = one_third * 3.0;
System.printf(one == 1.0); // prints "false" !!!!
因此，当您做任何涉及浮点值比较的事情时，都需要考虑到在计算中舍入误差的可能性。
有关此主题的更多信息，请阅读以下内容：
[就像其他人提到的一样，双精度型具有精度limit。
您可能考虑做的是更改此行else if (key == a[mid])。
并且可以代替引入严格的==，而尝试引入“足够好”的条件。例如
// 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;
...
加倍是确切数字吗？
比较双精度数和整数时，十进制值的变化会使比较语句为假。
比较时，一种解决方法可以将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