arrays - 如何找到最小值和最大值之间的子数组

Question

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

{4,7,9,12,23,34,56,78} 给定最小值和最大值，我想以高效的方式在数组中找到介于最小值和最大值之间的元素。

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 指数搜索？

Answer 1

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

二进制搜索基本上每次迭代都会将搜索空间减少一半。鉴于您的第一个示例 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) 时间差将无关紧要。

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