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

我有一个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）。间隔分别。