Powiedzmy, że masz posortowaną tablicę liczb całkowitych:

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

I chcesz znaleźć liczbę całkowitą, która mieści się w zakresie 4 i 23.

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

Tak więc wynik byłby 9.

Napisałem implementację binarysearch, ale nie jestem pewien, jak ją zmodyfikowałbym, aby uwzględnić fakt, że może istnieć wiele liczb całkowitych pasujących do górnych granic zakresu.

Pomyślałem o dodaniu wartości logicznej w sygnaturze metody, aby zapytać, czy szukać górnych granic klucza, ale nie jestem pewien, czy można to zrobić jedną metodą, zachowując złożoność O (log (N)).

A może jest jakiś inny sposób na znalezienie # elementów w tym zakresie w posortowanej tablicy w czasie O (log (N))?

Oto, co mam do tej pory:

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