5

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

{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)

4

4 回答 4

3

它可以在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;

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

于 2013-12-20T12:44:07.253 回答
0

我不是在解释我已经给出了 java 中的代码，如果你想你可以改进它。

 public class Test {

public static int binSearch(int array[], int key, int left, int right,boolean lb)
{
int mid = left + (right-left)/2;
if (key < array[mid])
    return binSearch(array, key, left, mid-1,lb);
else if (key > array[mid])
    return binSearch(array, key, mid+1, right,lb);
else if (key == array[mid]){
    if(!lb){
    if(key==array[mid+1]){
        int ctr=mid+1;
        while(key==array[++ctr]);
        return ctr--;
      }
    else
        return mid;
    }
    else{
    if(key==array[mid-1]){
        int ctr=mid-1;
        while(key==array[--ctr]);
        return ctr++;
    }
    else
        return mid;
   }

}
return -0; // Not Found

}

public static void main(String[] args) {
int a[]={1,2,4,4,5,8,12,15,15,23,54};
int start=binSearch(a, 4, 0, a.length,true);
int end=binSearch(a, 15, 0, a.length,false);
System.out.println(end-start+1);// number are include
}

}

于 2013-03-08T11:40:03.957 回答
0

在二分搜索中，当您找到所需的数字或该数字不在列表中时，您将停止递归过程。
在这里，您必须修改二分搜索算法。从较低的范围开始，比如a，不断重复，直到找到小于a的数字。在这样做的同时保持两个指数低和高。如果您要比较的数字小于a，则更新低，否则更新高。现在你有了较低的索引，现在递归地应用这个过程来找到大于这个a的数字。该索引将给出起始索引。
现在，对上限做补充，你会得到结束索引。
答案是ending index - starting index + 1

imin = 0, imax = A.size()-1
low = 0, high = A.size()-1
while(imax >= imin)
{
   imid = mid(imin,imax)
   if(key < A[imid])
   {
       imax = imid -1
       high = imid
   }
   else if(key > A[imid])
   {
       imin = imid + 1
       low = imid
   }
   else 
   {
       high = imid
       break;
   }
 }

现在，一旦退出循环检查 if imin > imax，如果是，则下限索引将是 imax。imin = low否则，使用相同的键再次重复搜索imax = high，直到达到条件imin > imax。对上限重复相同的操作。
时间复杂度介于O(log(n))和O(n)

于 2013-03-08T11:04:06.790 回答
0

您需要一个修改过的二分搜索，它有一个参数是查找元素的第一个还是最后一个出现。
您必须自己编写修改后的 binsearch。

于 2013-03-08T11:14:23.010 回答