Cómo encontrar el número de ocurrencias de un número en una matriz ordenada en o (logn)

Question

Tengo una matriz ordenada de enteros. Dado un número, cómo encontrar el número de ocurrencias de ese número en o (logn) incluso en el peor de los casos.

Answer 1

Busca binaria del número, luego búsqueda binaria para el inicio y el final de la ejecución.

Answer 2

Haga una búsqueda binaria para el punto donde todos los elementos a la izquierda son más pequeños que su número y todos a la derecha son iguales o mayores y otro para el punto en que todos los elementos son más pequeños o iguales a la izquierda y más a la derecha.

En otras palabras: en una búsqueda, su "prueba" es <, mientras que en la otra búsqueda la prueba es <=.

Ambas búsquedas son log n, así que ese es tu total.

Por ejemplo, en C ++ las dos funciones que necesitaría son std::lower_bound y std::upper_bound - Parece que las funciones de búsqueda binarias de Java existentes (en colecciones) siempre intentan buscar un valor específico, por lo que probablemente tenga que implementar la búsqueda usted mismo si lo está utilizando.

¡Es importante que use una variante de búsqueda binaria que use solo un predicado binario! Si usa una variante que verifica si presiona una clave específica "por accidente" a veces terminará demasiado pronto para esta tarea específica.

Answer 3

Buscar los puntos de inserción de number + 0.5 y number - 0.5 Usando dos búsquedas binarias. El número de elementos con valor number En la lista está la diferencia de las posiciones (índices) de estos dos puntos de inserción.

Answer 4

Ejecute la función a continuación una vez como está y una vez con la condición if cambiada a if (a [Mid] <= val) y los cambios correspondientes en las llamadas recursivas. Los dos valores devueltos son la ocurrencia inicial y final del valor particular.

      int  binmin(int a[], int start, int end,int val )
        {
         if(start<end)
            {
            int mid = (start+end)/2;
            if(a[mid]>=val)
            {
                binmin(a,start,mid-1,val);
            }
            else if(a[mid]<val)
            {
                binmin(a,mid+1,end,val);
            }

    }
    else if(start>end)
            return start;



  }