如何查找在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如果不是更清楚的話。你的選擇！