Digamos que tienes una matriz ordenada de enteros:

{3,4,4,6,10,15,15,19,23,23,24,30}

Y desea encontrar el número de enteros que se encuentran dentro de un rango de 4 y 23.

{4,4,6,10,15,15,19,23,23}

Así el resultado sería 9.

Escribí una implementación de búsqueda binaria, pero no estoy seguro de cómo la modificaría para tener en cuenta el hecho de que puede haber varios enteros que coincidan con los límites superiores del rango.

Pensé en agregar un valor booleano en la firma del método para preguntar si buscar los límites superiores de la clave, pero no estoy seguro si se puede hacer en un solo método mientras se mantiene la complejidad de O (registro (N)).

¿O hay alguna otra manera de encontrar el número de elementos en ese rango en el arreglo ordenado en tiempo O (log (N))?

Esto es lo que tengo hasta ahora:

int start = rangeBinarySearch(arr, 4, false);
int end = rangeBinarySearch(arr, 23, true); // true would indicate that I want the position of the last occurrence of the key.

int totalInRange = (Math.abs(end) - Math.abs(start) -1)


private static int rangeBinarySearch(int[] items, int key, boolean lastIndex) {
    if(items == null)
        throw new IllegalArgumentException();

    int start = 0;
    int end = items.length - 1;

    while(start <= end) {
        int mIndex = (start + end) / 2;
        int middle = items[mIndex];

        if(middle < key)
            start = (mIndex +1);
        else if(middle > key)
            end = (mIndex -1);
        else
            return mIndex; // Possible something here to find the upper bounds?
    }

    return -(start +1);
}