在Java整数列表中查找与给定值最接近的数字

1. 概述

在Java中处理整数List时，我们常遇到一个问题：从列表中找出与给定值最接近的数字。

本教程将探索使用Java解决这个问题的多种方法。

2. 问题介绍

先明确问题定义：

给定一个整数List和一个目标值target，需要从List中找出与target最接近的数字。当多个数字距离相等时，选择索引最小的那个。

接下来快速理解数字与目标值之间的"距离"概念。

2.1. 数字间的距离

在此场景中，数字a和b的距离定义为它们差的绝对值：Distance = abs(a - b)

例如，给定target = 42，以下是与不同数字(n)的距离(D)：

n = 42 → D = abs(42 – 42) = 0
n = 100 → D = abs(42 – 100) = 58
n = 44 → D = abs(42 – 44) = 2
n = 40 → D = abs(42 – 40) = 2

可见，当target = 42时，数字44和40与目标的距离相同。

2.2. 理解问题本质

List中与target最接近的数字，就是所有元素中距离target最小的那个。 例如在列表：

[ 8, 100, 6, 89, -23, 77 ]

当target = 70时，最接近的数字是77。但当target = 7时，8（索引0）和6（索引2）距离相同（均为1）。此时选择索引较小的数字，因此预期结果是8。

为简化问题，**我们假设输入List非空且不为null**。我们将以这个整数列表为例，通过单元测试验证每种解决方案。

此外，为高效解决问题，我们将根据输入List是否已排序选择不同算法。现在设计测试用例覆盖所有场景：

当target(-100)小于列表最小值(-23)：result = -23
当target(500)大于列表最大值(100)：result = 100
当target(89)存在于列表：result = 89
当target(70)不存在于列表：result = 77
当多个数字(8和6)与target(7)距离相同(1)：result = 8

接下来进入代码实现。

3. 处理未排序列表

通常我们不知道输入列表是否已排序。先创建一个变量保存数字列表：

static final List<Integer> UNSORTED_LIST = List.of(8, 100, 6, 89, -23, 77);

显然这不是有序列表。下面用两种方法解决问题。

3.1. 使用循环

最直接的思路是遍历列表，计算每个数字与target的距离：

static int findClosestByLoop(List<Integer> numbers, int target) {
    int closest = numbers.get(0);
    int minDistance = Math.abs(target - closest);
    for (int num : numbers) {
        int distance = Math.abs(target - num);
        if (distance < minDistance) {
            closest = num;
            minDistance = distance;
        }
    }
    return closest;
}

代码逻辑：

初始化closest为列表首元素，minDistance记录当前最小距离
遍历列表，计算每个数字与target的距离
若当前距离小于minDistance，更新closest和minDistance
遍历结束后closest即为结果

验证该方法是否通过测试：

assertEquals(-23, findClosestByLoop(UNSORTED_LIST, -100));
assertEquals(100, findClosestByLoop(UNSORTED_LIST, 500));
assertEquals(89, findClosestByLoop(UNSORTED_LIST, 89));
assertEquals(77, findClosestByLoop(UNSORTED_LIST, 70));
assertEquals(8, findClosestByLoop(UNSORTED_LIST, 7));

所有测试用例通过，循环方案有效。

3.2. 使用Stream API

Java Stream API能简洁高效处理集合。下面用Stream API解决：

static int findClosestByStream(List<Integer> numbers, int target) {
    return numbers.stream()
      .min(Comparator.comparingInt(o -> Math.abs(o - target)))
      .get();
}

代码比循环方案更紧凑，解析其工作原理：

numbers.stream()将List<Integer>转为Stream<Integer>
min()根据自定义Comparator找最小元素
使用Comparator.comparingInt()和lambda表达式创建比较器，比较依据是数字与target的距离（o -> Math.abs(o - target)）
min()返回Optional，因列表非空，直接调用get()获取结果

验证流式方案：

assertEquals(-23, findClosestByStream(UNSORTED_LIST, -100));
assertEquals(100, findClosestByStream(UNSORTED_LIST, 500));
assertEquals(89, findClosestByStream(UNSORTED_LIST, 89));
assertEquals(77, findClosestByStream(UNSORTED_LIST, 70));
assertEquals(8, findClosestByStream(UNSORTED_LIST, 7));

测试通过，流式方案简洁有效。

3.3. 性能分析

无论是循环还是流式方案，**都需遍历整个列表一次，时间复杂度均为O(n)**。

两种方案均不依赖列表顺序，因此无论输入列表是否排序都能正常工作。

但如果已知输入列表已排序，可采用更高效的算法。接下来探讨优化方案。

4. 处理已排序列表

**当列表已排序时，可使用二分查找算法，将时间复杂度降至O(log n)**。

先创建有序列表：

static final List<Integer> SORTED_LIST = List.of(-23, 6, 8, 77, 89, 100);

实现基于二分查找的解决方案：

public static int findClosestByBiSearch(List<Integer> sortedNumbers, int target) {
    int first = sortedNumbers.get(0);
    if (target <= first) {
        return first;
    }
 
    int last = sortedNumbers.get(sortedNumbers.size() - 1);
    if (target >= last) {
        return last;
    }
 
    int pos = Collections.binarySearch(sortedNumbers, target);
    if (pos > 0) {
        return sortedNumbers.get(pos);
    }
    int insertPos = -(pos + 1);
    int pre = sortedNumbers.get(insertPos - 1);
    int after = sortedNumbers.get(insertPos);
 
    return Math.abs(pre - target) <= Math.abs(after - target) ? pre : after;
}

代码解析：

处理边界情况：
- target ≤ 最小值（首元素）→ 返回首元素
- target ≥ 最大值（末元素）→ 返回末元素
**调用Collections.binarySearch()查找target位置pos**：
- pos > 0：精确匹配，直接返回该元素
- pos < 0：未找到，pos = -insertPos - 1（insertPos为插入点）
未匹配时，比较插入点前后两个元素的距离，返回距离较小的元素

验证二分查找方案：

assertEquals(-23, findClosestByBiSearch(SORTED_LIST, -100));
assertEquals(100, findClosestByBiSearch(SORTED_LIST, 500));
assertEquals(89, findClosestByBiSearch(SORTED_LIST, 89));
assertEquals(77, findClosestByBiSearch(SORTED_LIST, 70));
assertEquals(6, findClosestByBiSearch(SORTED_LIST, 7));

注意：当target = 7时，预期结果是6而非8，**因为在有序列表中6的索引(1)小于8的索引(2)**。

5. 总结

本文探讨了从整数列表中查找与给定值最接近数字的两种方法： ✅ 未排序列表：循环或Stream API（时间复杂度O(n)） ✅ 已排序列表：二分查找（时间复杂度O(log n)）

实际开发中，根据数据是否有序选择合适算法，避免在有序数据上使用O(n)方案。完整示例代码可在GitHub获取。

Persistence

REST

Security