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

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) 更快的方法搜索数组，并确定 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 大于每个元素)，但正如您可能知道的那样，这并不能证明不存在错误。