Java实现findInterval方法及自定义Interval类的相关问题咨询

核心疑问解答 #

• findInterval方法的返回值是自定义Interval类的实例对象，该对象封装了最终计算得到的最小索引范围的上下界两个值，调用方拿到实例后直接调用getLower()、getUpper()即可获取对应的范围数值。
• getLower()和getUpper()方法的返回类型为int，所有返回值都属于整数范畴：合法数组下标（0到n-1的正整数）、特殊标记值-1（存在目标值小于数组首元素）、特殊标记值n（存在目标值大于数组尾元素），用int类型完全匹配需求。

具体实现步骤 #

1. 实现Interval类 #

该类仅需做基础的数值封装即可，参考代码如下：

public class Interval {
    private final int lowerBound;
    private final int upperBound;

    // 构造方法传入计算得到的上下界
    public Interval(int lowerBound, int upperBound) {
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
    }

    public int getLower() {
        return lowerBound;
    }

    public int getUpper() {
        return upperBound;
    }
}

2. 实现findInterval核心逻辑 #

利用排序数组的特性，使用二分查找计算每个目标值的插入位置，整体时间复杂度为O(m log n)，其中m为目标值数量、n为排序数组长度，是符合要求的高效实现：

import java.util.Arrays;
import java.util.List;

public class IntervalFinder {
    public static <T extends Comparable<? super T>>
    Interval findInterval(T[] sortedData, List<T> targetValues) {
        int n = sortedData.length;
        // 边界情况处理：空数组直接返回[-1, 0]，可根据需求调整为抛异常
        if (n == 0 || targetValues.isEmpty()) {
            return new Interval(-1, 0);
        }

        int minInsertPos = n;
        int maxInsertPos = -1;
        boolean hasValueSmallerThanHead = false;
        boolean hasValueLargerThanTail = false;

        for (T target : targetValues) {
            int searchRes = Arrays.binarySearch(sortedData, target);
            // 计算目标值的插入位置：找到则返回元素下标，未找到返回应该插入的下标
            int insertPos = searchRes >= 0 ? searchRes : -(searchRes + 1);

            // 标记存在小于数组首元素的目标值
            if (insertPos == 0) {
                hasValueSmallerThanHead = true;
            }
            // 标记存在大于数组尾元素的目标值
            if (insertPos == n) {
                hasValueLargerThanTail = true;
            }

            // 更新全局最小/最大插入位置
            if (insertPos < minInsertPos) {
                minInsertPos = insertPos;
            }
            if (insertPos > maxInsertPos) {
                maxInsertPos = insertPos;
            }
        }

        // 按照需求调整边界值
        int finalLower = hasValueSmallerThanHead ? -1 : minInsertPos;
        int finalUpper = hasValueLargerThanTail ? n : maxInsertPos;

        return new Interval(finalLower, finalUpper);
    }
}

验证示例 #

你给出的测试用例：排序数组为[5,8,10,13,15,20,22,26]，目标值为[8,2,9,17]，运行上述代码后得到的finalLower为-1、finalUpper为5，和预期结果完全一致。

内容的提问来源于stack exchange，提问作者aldrich19