java - 如何对排序数组使用二分搜索来查找特定范围内的整数个数。 (重复)

Question

假设您有一个排序的整数数组:

{3,4,4,6,10,15,15,19,23,23,24,30}

并且您想找出落在 4 到 23 范围内的整数的个数。

{4,4,6,10,15,15,19,23,23}

因此结果为 9。

我写了一个二进制搜索实现，但我不确定如何修改它以同时考虑到可以有多个整数与范围上限匹配的事实。

我想在方法签名中添加一个 boolean 值来询问是否寻找键的上限，但我不确定是否可以在保持 O(log(N)) 的情况下在单个方法中完成复杂性。

或者是否有其他方法可以在 O(log(N)) 时间内找到排序数组中该范围内的项目数？

这是我目前所拥有的:

int start = rangeBinarySearch(arr, 4, false);
int end = rangeBinarySearch(arr, 23, true); // true would indicate that I want the position of the last occurrence of the key.

int totalInRange = (Math.abs(end) - Math.abs(start) -1)


private static int rangeBinarySearch(int[] items, int key, boolean lastIndex) {
    if(items == null)
        throw new IllegalArgumentException();

    int start = 0;
    int end = items.length - 1;

    while(start <= end) {
        int mIndex = (start + end) / 2;
        int middle = items[mIndex];

        if(middle < key)
            start = (mIndex +1);
        else if(middle > key)
            end = (mIndex -1);
        else
            return mIndex; // Possible something here to find the upper bounds?
    }

    return -(start +1);
}

Answer 1

下限和上限的范围二分搜索不同。这里不同意味着他们有不同的停止标准和返回步骤。

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[] = {3,4,4,6,10,15,15,19,23,23,24,30};
    int length = sizeof(arr)/sizeof(arr[0]);

    int left_range = 4;
    int right_range = 23;
    int index_left = binarySearchForLeftRange(a, length, left_range); // will be 1
    int index_right = binarySearchForRightRange(a, length, right_range); // will be 9

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

---

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