在排序列表中找到最近/最接近的值

Question

我想知道是否有可能在排序的 List 中为不在 列表中的元素找到最接近的元素。

例如，如果我们有值 [1,3,6,7] 并且我们正在寻找最接近 4 的元素，它应该返回 3，因为 3 是数组中最大的数字，它小于 4。

我希望这是有道理的，因为英语不是我的母语。

原文由 drBet 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

由于集合已排序，您可以在 O( log n ) 中进行修改后的二进制搜索：

     public static int search(int value, int[] a) {

        if(value < a[0]) {
            return a[0];
        }
        if(value > a[a.length-1]) {
            return a[a.length-1];
        }

        int lo = 0;
        int hi = a.length - 1;

        while (lo <= hi) {
            int mid = (hi + lo) / 2;

            if (value < a[mid]) {
                hi = mid - 1;
            } else if (value > a[mid]) {
                lo = mid + 1;
            } else {
                return a[mid];
            }
        }
        // lo == hi + 1
        return (a[lo] - value) < (value - a[hi]) ? a[lo] : a[hi];
    }

由于上面的大部分代码都是二进制搜索，您可以利用标准库中提供的 binarySearch(...) 并检查 insertion point 的值：

     public static int usingBinarySearch(int value, int[] a) {
        if (value <= a[0]) { return a[0]; }
        if (value >= a[a.length - 1]) { return a[a.length - 1]; }

        int result = Arrays.binarySearch(a, value);
        if (result >= 0) { return a[result]; }

        int insertionPoint = -result - 1;
        return (a[insertionPoint] - value) < (value - a[insertionPoint - 1]) ?
                a[insertionPoint] : a[insertionPoint - 1];
    }

原文由 David Soroko 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

你需要 Array.binarySearch ， 文档。

返回：搜索键的索引，如果它包含在数组中；否则，(-(插入点) - 1)。插入点定义为将键插入数组的点：大于键的第一个元素的索引，如果数组中的所有元素都小于指定键，则为 a.length。

原文由 Andrey 发布，翻译遵循 CC BY-SA 3.0 许可协议