查找两个数组值之间的值

Question

我希望我的函数采用值 x 并找到如下所示的数组值之间的值：

double[] xlist = {51.8, 10.3, 5.1, 2.6, 1.7, 1.29, 1.03, 0.86, 0.65, 0.52, 0.43, 0.37, 0.32, 0.29};

例1：当x = 1.5时，高值等于1.7，低值等于1.29
例2：当x = 12时，高值为51.8，低值为10.3

我正在使用二分法的派生方法来查找这些 "high" 和 "low" 值，但我的代码有问题。我的代码如下所示：

public static void main(String[] args){
    double[] xlist = {51.8, 10.3, 5.1, 2.6, 1.7, 1.29, 1.03, 0.86, 0.65, 0.52, 0.43, 0.37, 0.32, 0.29};
    double x = 0.9; //or whatever declare x to equal
    int high = xlist.length;
    int mid = 0, low = 0;
    while (low != high) {
            mid = (low + high) / 2;
                if (xlist[mid] > x) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
    System.out.println(xlist[mid - 1] + "\n" + x + "\n" + xlist[mid]);
  }

我的控制台输出如下所示：

51.8
12.0
10.3

它有效，但是当我将 x 值更改为 9.9 时，我得到：

5.1
9.9
2.6

我做错了什么？非常感谢任何帮助。

Answer 1

当您除 (low + high)/2 时，您将结果分配给 int 值并丢失了一些数据。我在下面所做的是将 high、mid 和 low 的数据类型更改为 "double"，然后在引用双精度数组中的元素时将值转换为 int。请尝试下面的代码。

        double[] xlist = {51.8, 10.3, 5.1, 2.6, 1.7, 1.29, 1.03, 0.86, 0.65, 0.52, 0.43, 0.37, 0.32, 0.29};
        double x = 9.9; //or whatever declare x to equal
        double high = xlist.length;
        double mid = 0.0, low = 0.0;
        while (low != high) {
                mid = (low + high) / 2;
                    if (xlist[(int)mid] > x) {
                        low = mid + 1;
                    } else {
                        high = mid;
                    }
                }
        System.out.println(xlist[(int)mid - 1] + "\n" + x + "\n" + 
xlist[(int)mid]);

Answer 2

我建议一个更简单的方法：

对数组进行排序
使用Arrays.binarySearch(xlist, x)找到可以插入x的位置p
如果p >= 0，x在数组中的那个位置
如果p < 0，-p-1是大于x的最小元素的位置，-p-2是小于x的最大元素的位置x.

确保添加相关检查（是 -p-2>=0 等）

Answer 3

出现问题是因为您正在更新 mid、测试，然后更改 low 或 high 索引。如果循环在更新 high = mid 后退出，那么 mid 值等于 low 索引并且一切正常 mid == low == high。如果循环在更新 low = mid + 1 后退出，则 mid 等于 low，但现在 mid == low-1 == high-1。这会导致有时会出现差一错误。

如果搜索在数组末尾附近运行，代码也会受到 ArrayIndexOutOfBoundsException 的影响。这是由于访问 xlist[mid-1]，其中 mid 可以到达 0。 high 索引从数组末尾后的一个位置开始，如果用作索引也会生成 ArrayIndexOutOfBoundsException.

更好的解决方案是从 0 开始 low 并从 xlist.length-1 开始 high，然后循环直到 low 和 high 限制相隔 1 个索引。那时，它们正是您正在寻找的边界：

    int low = 0, high = xlist.length - 1;
    while (high - low > 1) {
        int mid = (low + high) / 2;
        if (xlist[mid] > x) {
            low = mid;
        } else {
            high = mid;
        }
    }
    System.out.println(xlist[low] + "\n" + x + "\n" + xlist[high]);

查找两个数组值之间的值

Find value between two array values

java

arrays

bisection