Effizient algo, um die Anzahl der ganzen Zahlen in einem sortierten Array zu finden, die in einem bestimmten Bereich in O (log (N)) Zeit liegen?

Sie können das Konzept der binären Suche verwenden, um den Anfangs- und Endindex zu finden:

• Um den Startindex zu finden, halbieren Sie das Array, wenn der Wert gleich oder größer als die Eingabezahl ist, wiederholen Sie mit der unteren Hälfte des Arrays, andernfalls wiederholen Sie mit der höheren Hälfte. Stoppen Sie, wenn Sie ein Array der Größe 1 erreicht haben.
• Um den Startindex zu finden, halbieren Sie das Array, wenn der Wert größer als die Eingabezahl ist, wiederholen Sie mit der unteren Hälfte des Arrays, andernfalls mit der höheren Hälfte wiederholen. Stoppen Sie, wenn Sie ein Array der Größe 1 erreicht haben.

Beachten Sie, dass wir, wenn wir ein Array der Größe 1 erreicht haben, eine Zelle neben der Eingabe-Nummer sein können, also prüfen wir, ob sie gleich der Eingabe-Nummer ist. Wenn nicht, fixieren wir den Index, indem wir 1 aus dem Index addieren wir haben gefunden.

Und das ganze Verfahren:

Klingt wie eine binäre Suche - Log-Graphen zeigen den Effekt der "Halbierung" bei jedem Inkrement, was im Grunde eine binäre Suche ist.

Pseudocode:

Ist das klar genug, um von dort zu gehen?

Die Lösung besteht darin, das Array gleichzeitig zu durchsuchen (muss nicht gleichzeitig sein: P). Der Schlüssel ist, dass die Suche nach links und rechts leicht unterschiedlich ist. Für die rechte Seite, wenn Sie einen Betrogenen treffen, müssen Sie nach rechts suchen, und für die linke Seite, wenn Sie einen Betrogenen treffen, suchen Sie nach links. Was Sie suchen, ist die Grenze, also auf der rechten Seite, nach der Sie suchen.

Dies ist die Grenze und auf der linken Seite suchen Sie nur nach der Grenze in der entgegengesetzten Richtung. Am Ende geben Sie die Indizes der Grenzen zurück.

Da noch niemand einen funktionierenden Code veröffentlicht hat, werde ich einige (Java) posten:

Es mag ein Fehler an meinem Ende sein, aber Ron Tellers Antwort hat eine Endlosschleife, wenn ich sie getestet habe. Hier ist ein funktionierendes Beispiel in Java, das hier getestet werden kann, wenn Sie searchRange ändern. funktionieren nicht statisch.