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

Question

我有大量整数数组（大小在 10'000 到 1'400'000 之间）。我想让第一个整数大于一个值。该值永远不会在数组内。我一直在寻找各种解决方案，但我只发现：估计每个值并且不是为排序列表或数组设计的方法（时间复杂度为 O(n)）。递归的和/或不是为非常大的列表或数组设计的方法（虽然在其他语言中具有 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

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

那么这里是一种使用映射而不是数组的方法。

      int categorizer = 10_000;

      // Assume this is your array of ints.

      int[] arrayOfInts = r.ints(4_000, 10_000, 1_400_000).toArray();

您可以像这样将它们分组在地图中。

       Map<Integer, List<Integer>> ranges =

            Arrays.stream(arrayOfInts).sorted().boxed().collect(

                  Collectors.groupingBy(n -> n / categorizer));

现在，当你想找到下一个更高的元素时，你可以获得包含该数字的列表。

假设您想要下一个大于 982,828 的数字

      int target = 982,828;

      List<Integer> list = map.get(target/categorizer); // gets the list at key = 98

现在只需使用您喜欢的方法处理列表即可。一张纸条。在某些情况下，您的最高数字可能会出现在紧随其后的其他列表中，具体取决于差距。您需要考虑到这一点，也许可以通过调整数字的分类方式或搜索后续列表来解决。但这可以大大减少您正在使用的列表的大小。