确定与数组中的间隔匹配的值的最快方法

Question

我有一个int从x到的排序数组y（元素的值是随机的，但使用升序排列qsort()）。程序接收各种间隔，例如<10;50>或<50;100>。我有以下简单for循环来确定数组中的值是否在设置的时间间隔内，如果是，则将其添加到计数器中。

 for(int i = 0; i < arraySize ;i++ )  {        
       if (points[i] >= interval1 && points[i] <= interval2){
            counter++;               
        }
    }

我需要比O(n)在数组中搜索并确定in points[i]中的值是否在设置的时间间隔中更快的方法。该值可以是数百万，因此会大大降低。

数组中的元素范围可以从0到1000000000（1e9）。间隔分别。

Answer 1

使用二分查找 - 对于输入区间[i, j]，找到大于 的最小整数的索引i，找到小于 的最大整数的索引j，然后返回它们之间的距离。

ssize_t bin_search_first_larger(int arr[], size_t arr_sz, int val) {
    ssize_t l = -1;
    ssize_t r = arr_sz;
    /* invariant: arr[l] < val && val <= arr[r] */
    while (l+1 != r) {
        ssize_t m = l+(r-l)/2;
        if (arr[m] < val) {
            l = m;
        } else {
            r = m;
        }
    }
    /* l+1 == r && arr[l] < val && val <= arr[r] */
    return r;
}

ssize_t bin_search_last_smaller(int arr[], size_t arr_sz, int val) {
    ssize_t l = -1;
    ssize_t r = arr_sz;
    /* invariant: arr[l] <= val && val < arr[r] */
    while (l+1 != r) {
        ssize_t m = l+(r-l)/2;
        if (arr[m] <= val) {
            l = m;
        } else {
            r = m;
        }
    }
    /* l+1 == r && arr[l] <= val && val < arr[r] */
    return l;
}

ssize_t values_in(int arr[], size_t arr_sz, int x, int y) {
    ssize_t i = bin_search_first_larger(arr, arr_sz, x);
    ssize_t j = bin_search_last_smaller(arr, arr_sz, y);
    return j-i+1;
}

二分搜索代码改编自 Jon Bentley 的《Programming Pearls》（非常值得一读），其中展示了如何修改二分搜索以返回具有重复项的排序数组中某个值的第一次出现或最后一次出现（而不是返回任意出现的重复值）。对于您的用例，该过程类似，但差异很细微。

请注意，从概念上讲，假设 是arr[-1]负无穷大，并且arr[N]是正无穷大（其中N是数组的大小），但显然，代码从不尝试访问此类元素。

时间复杂度是O(log(N))数组N的大小，很难（不可能？）比这更好。

我运行了一些测试，它似乎适用于一般情况和边缘情况（范围内没有元素，或y大于每个元素，或x小于每个元素，或既x小于每个元素又y大于每个元素） ，但正如您可能知道的那样，这并不能证明不存在错误。