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

Question

获取数组中两个边界之间的所有值的最快方法是什么。这两个界限都是包容的。在数组中，可以有重复项，在这种情况下，它应该返回所有值。例如，如果我有array：[1 1 3 3 4 6 7 7 8 10]和界限[2, 7]，程序将返回[3 3 4 6 7 7]。我知道我可以做一个循环，遍历每个元素以检查它是否在范围之内，但是我想知道是否有更快的方法。数组已排序，因此我考虑过进行二进制搜索，但不确定如何运行。

Answer 1

由于数组已排序，因此您要在数组的中间寻找一个切片。因此，您需要找到数组中最低界限的位置，然后找到上限的相同位置（从末尾开始）。这些位置之间的数组元素是结果数组。

您基本上在开始和结束时都截去了不需要的数字：

    int[] arr = new int[]{1, 1, 3, 3, 4, 6, 7, 7, 8, 10};

    int low=2;

    int up=7;

    int lowIdx=0;

    int upIdx=arr.length-1;

    for(int i=0;i<arr.length;i++){

        lowIdx = i;

        if(arr[i] >= low){

            break;

        }

    }

    for(int i = arr.length-1;i>=0;i--){

        if(arr[i] <= up){

            break;

        }

        upIdx = i;

    }

    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。循环周期：

        int minIndex = arr.length;

        int maxIndex = 0;

        for(int i = 0; i < arr.length / 2; i++)

        {

            if(arr[i] >= min && i < minIndex)

                minIndex = i;

            int j = arr.length-i-1;

            if(arr[j] <= max && j > maxIndex)

                maxIndex = j;

        }

        int[] res = Arrays.copyOfRange(arr,minIndex,maxIndex+1);