java - 如何在 O(log(N)) 时间内查找排序数组中一定范围内的整数个数？

Question

我有一个排序的整数数组:

{1,2,4,4,5,8,12,15,15,23,54}

我想找出该数组中有多少数字落在一个范围内，比如 4 到 15。

{4,4,5,6,12,15,15}

因此，数组中有 7 个项目在该范围内。

我需要在 O(log(N)) 时间内完成此操作，并且我认为我可以使用二进制搜索，但由于重复项而无法找到下限和上限。

如何在 O(log(N)) 时间内完成？

我想过从前面开始循环，然后从最后开始循环，但这可能达到 O(N)

Answer 1

通过范围二分查找下界和上界可以在O(logN)时间内完成。下限和上限的范围二分搜索不同。这里不同意味着他们有不同的停止标准和返回步骤。

1. 对于下界(左范围)，可以调用以下函数获取排序数组中大于或等于它的索引，否则为-1。

   int binarySearchForLeftRange(int a[], int length, int left_range)
   {
       if (a[length-1] < left_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] >= left_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return high+1;
   }
   

2. 对于上界(右范围)，可以调用以下函数获取排序数组中小于或等于它的索引，否则为-1。

   int binarySearchForRightRange(int a[], int length, int right_range)
   {
       if (a[0] > right_range)
           return -1;
   
       int low = 0;
       int high = length-1;
   
       while (low<=high)
       {
           int mid = low+((high-low)/2);
   
           if(a[mid] > right_range)
               high = mid-1;
           else //if(a[mid]<i)
               low = mid+1;
       }
   
       return low-1;
   }
   

3. 最后，如果你想得到这个范围内有多少个元素，根据上面这两个函数的返回值很容易。

   int index_left = binarySearchForLeftRange(a, length, left_range);
   int index_right = binarySearchForRightRange(a, length, right_range);
   
   if (index_left==-1 || index_right==-1 || index_left>index_right)
       count = 0;
   else
       count = index_right-index_left+1;
   

---

测试:(重复)

    int a[] = {1,2,4,4,5,8,12,15,15,23,54};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 15;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 2
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 8

    int count; // will be 7
    if (index_left==-1 || index_right==-1 || index_left>index_right)
        count = 0;
    else
        count = index_right-index_left+1;

---

编辑:当然，您可以通过传递一个额外的标志来将前两个函数合并为一个，以指示它是下限还是上限，但如果不这样做会更清楚。您的选择!