Допустим, у вас есть отсортированный массив целых чисел:

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

И вы хотите найти количество целых чисел, которые находятся в диапазоне от 4 до 23.

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

Таким образом, результат будет 9.

Я написал реализацию двоичного поиска, но я не уверен, как бы я изменил ее, чтобы учесть тот факт, что может быть несколько целых чисел, которые соответствуют верхним границам диапазона.

Я думал о добавлении логического значения в сигнатуру метода, чтобы спросить, нужно ли искать верхние границы ключа, но я не уверен, что это можно сделать одним методом, сохраняя сложность O (log (N)).

Или есть какой-то другой способ найти количество элементов в этом диапазоне в отсортированном массиве за O (log (N)) времени?

Это то, что я до сих пор:

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