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

标签 java search arraylist binary-search

这是一种修改后的二分搜索,它返回排序数组列表中与给定值最接近的元素。我如何调整它,以便它可以返回 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 作为下一个值。

最佳答案

此代码使用一种非常简单的方法,根据 lohimid 值之间的差异将元素添加到结果列表中。

在边缘情况下,返回的元素数量可能小于 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;
}

关于java - 在排序数组列表中查找 2 个最近的前一个值和 2 个最近的下一个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49099605/

相关文章:

search - "1 of n"Emacs 搜索结果

java - 比较两个数组列表并在第二个数组列表中取出不常见的内容

java - Arraylist 无法与游标查询一起正常工作

jQuery UI 自动完成 : return "nothing found" when no search matches occur

java - HTTP 状态 500 - java.net.ConnectException : Connection refused: connect

java - 未找到产品名称 : [Impala] 的数据库类型

java - 使用 XPath Java 设置节点值

C++:具有两个相关键的快速结构

java - 以 ArrayList 作为参数相乘列表元素的方法

java - 使用未标记的break语句会导致编译失败