Algorithmen und Datenstrukturen · Senior · Frage 37 von 75
Eine virtualisierte Liste rendert nur sichtbare Zeilen von 100.000 Elementen unterschiedlicher Höhe. Wie findet sie schnell die erste sichtbare Zeile?
- 1Binäre Suche über kumulierte Zeilen-Offsets
- 2Bei jedem Scrollen die Zeilen von oben durchlaufen
- 3scrollTop durch die durchschnittliche Zeilenhöhe teilen
Antwort zeigen
Richtige Antwort: Binäre Suche über kumulierte Zeilen-Offsets
Erklärung
Präfixsummen der Zeilenhöhen sind sortiert, binäre Suche findet die Zeile bei scrollTop also in O(log n). Durchlaufen ist O(n) pro Scrollen; durch einen Durchschnitt zu teilen driftet, wenn Höhen variieren.