Contare il numero di occorrenze di un numero in un array ordinato

Question

Il mio maestro mi ha dato il compito successivo:

On a sorted array, find the number of occurrences of a number. 
The complexity of the algorithm must be as small as possible. 

Questo è quello che ho pensato:

public static int count(int[] a, int x) 
{ 
    int low = 0, high = a.length - 1; 

    while(low <= high) 
    { 
     int middle = low + (high - low)/2; 

     if(a[middle] > x) { 
      // Continue searching the lower part of the array 
      high = middle - 1; 
     } else if(a[middle] < x) { 
      // Continue searching the upper part of the array 
      low = middle + 1; 
     } else { 
      // We've found the array index of the value 
      return x + SearchLeft(arr, x, middle) + SearchRight(arr, x, middle); 
     } 
    } 

    return 0; 
} 

SearchLeft e SearchRight iterarlo array, fino a quando il numero non viene visualizzato.

Non sono sicuro di aver raggiunto la scrittura del codice più veloce per questo problema e vorrei vedere altre opinioni.

Edit: Dopo qualche aiuto da commenti e risposte, questo è il mio tentativo in corso:

public static int count(int[] array, int value) 
{ 
    return SearchRightBound(array, value) - SearchLeftBound(array, value); 
} 

public static int SearchLeftBound(int[] array, int value) 
{ 
    int low = 0, high = array.length - 1; 

    while(low < high) 
    { 
     int middle = low + (high - low)/2; 

     if(array[middle] < value) { 
      low = middle + 1; 
     } 
     else { 
      high = middle; 
     } 
    } 

    return low; 
} 

public static int SearchRightBound(int[] array, int value) 
{ 
    int low = 0, high = array.length - 1; 

    while(low < high) 
    { 
     int middle = low + (high - low)/2; 

     if(array[middle] > value) { 
      high = middle; 
     } 
     else { 
      low = middle + 1; 
     } 
    } 

    return low; 
} 

Answer 1

SearchLeft e SearchRight iterano l'array, fino a quando il numero non viene visualizzato.

Ciò significa che se l'intero array è riempito con il valore di destinazione, l'algoritmo è O(n).

È possibile renderlo O(log n) nel caso peggiore se si esegue la ricerca binaria per la prima e l'ultima occorrenza di x.

// search first occurrence 
int low = 0, high = a.length - 1; 
while(low < high) { 
    int middle = low + (high-low)/2; 
    if (a[middle] < x) { 
     // the first occurrence must come after index middle, if any 
     low = middle+1; 
    } else if (a[middle] > x) { 
     // the first occurrence must come before index middle if at all 
     high = middle-1; 
    } else { 
     // found an occurrence, it may be the first or not 
     high = middle; 
    } 
} 
if (high < low || a[low] != x) { 
    // that means no occurrence 
    return 0; 
} 
// remember first occurrence 
int first = low; 
// search last occurrence, must be between low and a.length-1 inclusive 
high = a.length - 1; 
// now, we always have a[low] == x and high is the index of the last occurrence or later 
while(low < high) { 
    // bias middle towards high now 
    int middle = low + (high+1-low)/2; 
    if (a[middle] > x) { 
     // the last occurrence must come before index middle 
     high = middle-1; 
    } else { 
     // last known occurrence 
     low = middle; 
    } 
} 
// high is now index of last occurrence 
return (high - first + 1); 

Answer 2

Beh questo è essenzialmente ricerca binaria + a camminare verso i confini del l'intervallo della soluzione. L'unico modo per velocizzare questo è forse la cache degli ultimi valori di basso e alto e quindi usare la ricerca binaria per trovare anche i boarder, ma questo sarà davvero importante solo per intervalli molto grandi, nel qual caso è improbabile che tu abbia saltato proprio dentro