时间戳

首页 > 解决方案 > 二进制搜索适用于整数数组，但不适用于双精度数组

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

问题描述

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

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

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

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

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

谢谢！

标签： javabinary-search

解决方案

就像其他人提到的那样，双精度类型有一个精度限制。

您可能会考虑更改此行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; 
...

编辑：为了使二进制搜索算法起作用，数组必须是SORTED。二分搜索分治法背后的关键思想。

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

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

推荐阅读