Digamos que você tenha uma matriz ordenada de inteiros:

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

E você quer encontrar o número de inteiros que estão dentro de um intervalo de 4 e 23.

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

Assim, o resultado seria 9.

Escrevi uma implementação de binarysearch, mas não tenho certeza de como modificá-la para também levar em conta o fato de que pode haver vários inteiros que correspondem aos limites superiores do intervalo.

Pensei em adicionar um booleano na assinatura do método para perguntar se procuraria os limites superiores da chave, mas não tenho certeza se isso pode ser feito em um único método, mantendo a complexidade do O (log (N)).

Ou há alguma outra maneira de encontrar o número de itens nesse intervalo na matriz classificada no tempo O (log (N))?

Isto é o que eu tenho até agora:

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);
}