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

Question

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

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

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

Answer 1

由于数组已排序，因此您要在数组的中间寻找一个切片。因此，您需要找到数组中最低界限的位置，然后找到上限的相同位置（从末尾开始）。这些位置之间的数组元素是结果数组。您基本上在开始和结束时都截去了不需要的数字：&nbsp; &nbsp; int[] arr = new int[]{1, 1, 3, 3, 4, 6, 7, 7, 8, 10};&nbsp; &nbsp; int low=2;&nbsp; &nbsp; int up=7;&nbsp; &nbsp; int lowIdx=0;&nbsp; &nbsp; int upIdx=arr.length-1;&nbsp; &nbsp; for(int i=0;i<arr.length;i++){&nbsp; &nbsp; &nbsp; &nbsp; lowIdx = i;&nbsp; &nbsp; &nbsp; &nbsp; if(arr[i] >= low){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; for(int i = arr.length-1;i>=0;i--){&nbsp; &nbsp; &nbsp; &nbsp; if(arr[i] <= up){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; upIdx = i;&nbsp; &nbsp; }&nbsp; &nbsp; System.out.println(Arrays.toString(Arrays.copyOfRange(arr, lowIdx, upIdx)));印刷 [3, 3, 4, 6, 7, 7]这容易吗？并不真地。它是稍微复杂的代码，它利用了数组已排序的事实。

Answer 2

最简单的方法是：int[] arr = {1, 1, 3, 3, 4, 6, 7, 7, 8, 10};int min = 2;int max = 7;int[] result = IntStream.of(arr).filter(x -> x >= min && x <= max).toArray();这样做的另一种方法（在许多情况下比binarysearch需要遍历整个数组来找到最后一个索引要快）是使用一个循环，该过程只需要遍历一半的元素，并进行两次查找pr。循环周期：&nbsp; &nbsp; &nbsp; &nbsp; int minIndex = arr.length;&nbsp; &nbsp; &nbsp; &nbsp; int maxIndex = 0;&nbsp; &nbsp; &nbsp; &nbsp; for(int i = 0; i < arr.length / 2; i++)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[i] >= min && i < minIndex)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; minIndex = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int j = arr.length-i-1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(arr[j] <= max && j > maxIndex)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; maxIndex = j;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; int[] res = Arrays.copyOfRange(arr,minIndex,maxIndex+1);