Zeitkomplexität der eine Liste der Intervalle der Suche

Question

Lassen a ein Intervall[a.start, a.end], wo a.start und a.end sind reelle Zahlen, so dass 0 <= a.start < a.end <= 1.

Zwei solche Intervalle a und bschneiden wenn a.start < b.start < a.end ODER b.start <= a.start < b.end

As Lassen Sie eine sortierte Liste von nicht-schneidenden Intervallen sein a_0, a_1, ..., a_n so dass a_i nicht a_j und a_i.start < a_j.start für i < j

Da schneidet das Intervall b, bestimmen das erste Intervall und das letzte Intervall in As, dass b int (oder finde keine Schnittpunkte). dh: Wenn möglich, finden i und j, so dass b schneidet a_i und a_j aber nicht a_{i-1} oder a_{j+1}

---

ich dies mit einer modifizierten binären Suche gelöst habe (O (n) im schlechtesten Fall), Also meine Intuition ist, dass dies ein lg (n) Problem ist, aber ich weiß nicht, ob ich den besten Algorithmus habe.

Answer 1

Da Sie eine sortierte Liste von sich nicht überschneidenden Intervallen haben, wissen Sie, dass jedes Intervall endet, bevor das nächste Intervall beginnt. Sie können diese Liste auch als sortierte Liste von Intervallstartpunkten oder als sortierte Liste von Intervallende betrachten Punkte.

Ich denke, Sie können die binäre Suche auf einer sortierten Liste von Intervall Endpunkten verwenden, um den kleinsten Intervall Endpunkt zu finden, der mindestens so groß ist wie b.start in O (log n) worst case time, und dies ist die erstes Intervall, das b schneidet (falls irgendein Intervall b schneidet). Ähnlich hat das letzte Intervall, das b schneidet, den größten Startpunkt, der nicht größer als b.end ist, wenn irgendein Intervall b schneidet.

Um einen kleinsten Punkt zu finden, der mindestens so groß ist wie das Ziel, betrachten Sie den Punkt in der Mitte des Bereichs der möglichen Lösungen (nach Anzahl der möglichen Lösungen, nicht nach Position). Wenn dieser Punkt mindestens so groß ist wie das Ziel, erstreckt sich der Bereich der möglichen Lösungen von diesem Punkt nach links und schließt diesen Punkt ein. Wenn dieser Punkt nicht mindestens so groß ist wie das Ziel, erstreckt sich der Bereich der möglichen Lösungen von unmittelbar nach diesem Punkt nach rechts. In beiden Fällen haben Sie die Anzahl der möglichen Lösungen um etwa die Hälfte reduziert, so dass Sie den schlechtesten Fall O (log n) haben.