0

我有一个排序数组。让我们假设

{4,7,9,12,23,34,56,78} 给定 min 和 max 我想以有效的方式在 min 和 max 之间的数组中找到元素。

Cases:min=23 and max is 78  op:{23,34,56,78}
 min =10 max is 65 op:{12,23,34,56}

min 0 and max is 100 op:{4,7,9,12,23,34,56,78}

Min 30 max= 300:{34,56,78}

Min =100 max=300 :{} //empty

我想找到有效的方法来做到这一点？我不是在问代码任何我可以在这里使用的算法，比如 DP 指数搜索？

4

2 回答 2

3

由于它已排序，因此您可以通过对整个数组使用二进制搜索轻松找到大于或等于所需最小值的最低元素。

二进制搜索基本上每次迭代都会将搜索空间减少一半。鉴于您的第一个示例10，您从 的中点开始如下12：

 0  1  2  3  4  5  6  7 <- index
 4  7  9 12 23 34 56 78
         ^^

由于您正在查看的元素高于 10 并且次低的元素更小，因此您已经找到了它。

然后，您可以使用类似的二进制搜索，但只能在从您刚刚找到的元素到最后的那个部分上。这次您正在寻找小于或等于所需最大值的最高元素。

在与前面提到的相同示例中，您从以下内容开始：

 3  4  5  6  7 <- index
12 23 34 56 78
      ^^

由于小于 65 并且以下也是，因此您需要将指针增加到 的中点34..78：

 3  4  5  6  7 <- index
12 23 34 56 78
         ^^

你有它，因为那个数字更少，而后面的数字更多（超过 65）

然后，您可以从停止索引（3 和 6）开始提取值。

 0  1  2    3  4  5  6    7 <- index
 4  7  9 ((12 23 34 56)) 78
           -----------

该算法的时间复杂度为O(log N)。尽管请记住，这只有在处理更大的数据集时才变得重要。如果您的数据集确实只包含大约八个元素，那么您也可以使用线性搜索，因为（1）它会更容易编写；(2) 时间差将无关紧要。

我倾向于不担心时间复杂度，除非操作非常昂贵，数据集大小达到数千，或者我必须每秒执行数千次。

于 2013-09-18T09:34:54.750 回答
2

由于已排序，因此应该这样做：

List<Integer> subarray = new ArrayList<Integer>();

for (int n : numbers) {
    if (n >= MIN && n <= MAX) subarray.add(n);
}

这是 O(n)，因为您只查看每个数字一次。

于 2013-09-18T09:38:48.057 回答