这种获取排序列表中最接近数字的方法是否最有效？

Question

我有大量整数数组（大小在 10'000 到 1'400'000 之间）。我想让第一个整数大于一个值。该值永远不会在数组内。

我一直在寻找各种解决方案，但我只发现：

1. 估计每个值并且不是为排序列表或数组设计的方法（时间复杂度为 O(n)）。

2. 递归的和/或不是为非常大的列表或数组设计的方法（虽然在其他语言中具有 O(n) 或更多时间复杂度，所以我不确定）。

我设计了自己的方法。这里是 ：

int findClosestBiggerInt(int value, int[] sortedArray) {

    if( sortedArray[0]>value ||

            value>sortedArray[sortedArray.length-1] )   // for my application's convenience only. It could also return the last.

        return sortedArray[0];

    int exp = (int) (Math.log(sortedArray.length)/Math.log(2)),

        index = (int) Math.pow(2,exp);

    boolean dir; // true = ascend, false = descend.

    while(exp>=0){

        dir = sortedArray[Math.min(index, sortedArray.length-1)]<value;

        exp--;

        index = (int)( index+ (dir ? 1 : -1 )*Math.pow(2,exp) );

    }

    int answer = sortedArray[index];

    return answer > value ? answer : sortedArray[index+1];

}

它具有 O(log n) 时间复杂度。对于长度为 1'400'000 的数组，它将在 while 块内循环 21 次。不过，我不确定它是否可以改进。

没有外部包的帮助，有没有更有效的方法？节省任何时间都是很好的，因为这种计算经常发生。

Answer 1

没有外部包的帮助，有没有更有效的方法？节省任何时间都是很好的，因为这种计算经常发生。那么这里是一种使用映射而不是数组的方法。&nbsp; &nbsp; &nbsp; int categorizer = 10_000;&nbsp; &nbsp; &nbsp; // Assume this is your array of ints.&nbsp; &nbsp; &nbsp; int[] arrayOfInts = r.ints(4_000, 10_000, 1_400_000).toArray();您可以像这样将它们分组在地图中。&nbsp; &nbsp; &nbsp; &nbsp;Map<Integer, List<Integer>> ranges =&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Arrays.stream(arrayOfInts).sorted().boxed().collect(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Collectors.groupingBy(n -> n / categorizer));现在，当你想找到下一个更高的元素时，你可以获得包含该数字的列表。假设您想要下一个大于 982,828 的数字&nbsp; &nbsp; &nbsp; int target = 982,828;&nbsp; &nbsp; &nbsp; List<Integer> list = map.get(target/categorizer); // gets the list at key = 98现在只需使用您喜欢的方法处理列表即可。一张纸条。在某些情况下，您的最高数字可能会出现在紧随其后的其他列表中，具体取决于差距。您需要考虑到这一点，也许可以通过调整数字的分类方式或搜索后续列表来解决。但这可以大大减少您正在使用的列表的大小。