Angenommen, Sie haben ein sortiertes Array von Ganzzahlen:

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

Und Sie möchten die Anzahl der Ganzzahlen ermitteln, die im Bereich von 4 bis 23 liegen.

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

Das Ergebnis wäre also 9.

Ich habe eine Implementierung von binarysearch geschrieben, bin mir aber nicht sicher, wie ich sie ändern würde, um auch die Tatsache zu berücksichtigen, dass es mehrere Ganzzahlen geben kann, die mit den oberen Grenzen des Bereichs übereinstimmen.

Ich dachte daran, der Methodensignatur einen Booleschen Wert hinzuzufügen, um zu fragen, ob nach den oberen Schranken des Schlüssels gesucht werden soll, bin mir aber nicht sicher, ob dies in einer einzelnen Methode möglich ist, während die Komplexität von O (log (N)) beibehalten wird.

Oder gibt es eine andere Möglichkeit, die Anzahl der Elemente in diesem Bereich im sortierten Array in O (log (N)) zu finden?

Das habe ich bisher:

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