如何查找在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

在二进制搜索，您停止递归过程，当你找到需要的号码或当号码不在列表中时。
在这里，您必须修改二进制搜索算法。从较低范围开始，例如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; 
    } 
} 

现在，一旦它散发出来的回路校验，如果imin > imax，如果是，那么较低的范围内指数将是IMAX。否则，用imin = low和imax = high再次用相同的密钥再次搜索，直到达到条件imin > imax。重复相同的上限。
的时间复杂度降到O(log(n))和O(n)之间

Answer 2

您需要修改的二进制搜索，一个是有一个参数是否找到元素的第一个或最后一个实例。
你必须自己写修改过的binsearch。

Answer 3

我不解释我给了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 
} 

}

Answer 4

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

---

编辑：当然，你可以通过一个头两个功能合二为一额外的标志来表明它是下限还是上限，虽然它会是mu如果不是更清楚的话。你的选择！