java - 在排序数组列表中查找 2 个最接近的前一个值和 2 个最接近的下一个值

Question

这是一种改进的二分搜索，它返回排序数组列表中最接近给定值的元素。我如何调整它以便它可以返回最近的 2 个上一个元素和 2 个最近的下一个元素？

private static Long search(long value, ArrayList<Long> a) {

    if(value < a.get(0)) {
        return a.get(0);
    }
    if(value > a.get(a.size()-1)) {
        return a.get(a.size()-1);
    }

    int lo = 0;
    int hi = a.size() - 1;

    while (lo <= hi) {
        int mid = (hi + lo) / 2;
        if (value < a.get(mid)) {
            hi = mid - 1;
        } else if (value > a.get(mid)) {
            lo = mid + 1;
        } else {
            return a.get(mid);
        }
    }
    return (a.get(lo) - value) < (value - a.get(hi)) ? a.get(lo) : a.get(hi);
}

例如让我们考虑我的数组列表由这些元素组成:

[101, 201, 301, 401, 501, 601, 701, 801, 901, 1001]

我的值是 730。我希望搜索返回一个包含 4 个元素的数组，其中 601、701 作为前一个值，801 和 901 作为下一个值。

Answer 1

此代码使用一种非常直接的方法，根据 lo、hi 和 mid 值之间的差异向结果列表添加元素。

在边缘情况下，返回的元素数量可以小于 4。例如，如果左侧或右侧没有元素(因为列表边界)，则返回的列表大小可以是 2 或 3取决于最接近值的位置。

如果这是你想要的，那么这里是代码:

private static List<Long> search(long value, List<Long> a) {
    if (a.size() < 3) return new ArrayList<>(a);
    List<Long> result = new ArrayList<>();
    if (value < a.get(0)) {
        result.add(a.get(0));
        result.add(a.get(1));
        return result;
    }
    if (value > a.get(a.size() - 1)) {
        result.add(a.get(a.size() - 2));
        result.add(a.get(a.size() - 1));
        return result;
    }

    int lo = 0;
    int hi = a.size() - 1;
    int match = -1;

    while (lo <= hi) {
        int mid = (hi + lo) / 2;
        if (value < a.get(mid)) {
            hi = mid - 1;
        } else if (value > a.get(mid)) {
            lo = mid + 1;
        } else {
            match = mid;
            break;
        }
    }

    if (match >= 0) {
        if (match > 1) result.add(a.get(match - 2));
        if (match > 0) result.add(a.get(match - 1));
        if (match < a.size() - 1) result.add(a.get(match + 1));
        if (match < a.size() - 2) result.add(a.get(match + 2));
    } else if (a.get(lo) < value) {
        result.add(a.get(hi));
        result.add(a.get(lo));
        if (lo < a.size() - 1) result.add(a.get(lo + 1));
        if (lo < a.size() - 2) result.add(a.get(lo + 2));
    } else if (a.get(hi) > value) {
        if (hi > 1) result.add(a.get(hi - 2));
        if (hi > 0) result.add(a.get(hi - 1));
        result.add(a.get(hi));
        result.add(a.get(lo));
    } else {
        if (hi > 0) result.add(a.get(hi - 1));
        result.add(a.get(hi));
        result.add(a.get(lo));
        if (lo < a.size() - 1) result.add(a.get(lo + 1));
    }

    return result;
}