时间戳

首页 > 解决方案 > 在边界之间查找数组中所有整数的最快方法

java - 在边界之间查找数组中所有整数的最快方法

问题描述

获取数组中介于 2 个边界之间的所有值的最快方法是什么。这两个界限都是包容性的。在数组中，可以有重复项，在这种情况下，它应该返回所有值。

例如，如果我有数组：和程序将返回[1 1 3 3 4 6 7 7 8 10]的边界。[2, 7][3 3 4 6 7 7]

我知道我可以做一个循环并遍历每个元素以检查它是否在边界内，但我想知道是否有更快的方法。该数组已排序，因此我考虑过进行二进制搜索，但我不确定这将如何工作。

谢谢！

标签： javaarraysalgorithm

解决方案

您可以使用它Arrays.binarySearch(int[], key)来查找高边界元素和低边界元素，无论它们是否存在。给定 boundslow和high，该subRange()方法应该执行您想要的操作：

/* returns the index first/last occurrence of a value, or one past 
   where the element would have been if missing */
static int indexOf(int array[], int bound, boolean last) {
  int index = Arrays.binarySearch(array, bound);
  if (last && index >= 0) {
    while (index < array.length && array[index] == bound) index++;
  }
  return index < 0 ? -index - 1 : index;
}

static int subRange(int a[], int low, int high) {
  return Arrays.copyOfRange(a, indexOf(a, low, false), indexOf(a, high, true));
}

主要的尴尬是处理上限（last == true案例），因为返回第一个binarySearch元素的索引，因此您需要扫描以找到最后一个元素。我很确定那里有一个错误的地方，对于那些在不理解的情况下复制它的读者来说是一个惊喜。

一个小的额外优化是可能的，因为第二次搜索可以限制在第一次搜索找到的索引右侧的范围内，使用Arrays.binarySearch在数组的子范围上操作的版本。如果您想获得真正的硬核，您可以编写自己的自定义二进制搜索，它一次获取两个元素，并同时搜索两个元素：在搜索开始时，只要当前中点低于或高于您几乎免费地有效地缩小了这两个元素的范围（与单值搜索相比）。一旦mid拆分了低键和高键，您就可以使用当前范围作为起点进行单独的二进制搜索。low这在以下情况下特别有用high非常接近：有效地将搜索时间减半。

推荐阅读