Алгоритми та структури даних · Senior · Запитання 37 з 75
Віртуалізований список рендерить лише видимі рядки зі 100 000 елементів різної висоти. Як він швидко знаходить перший видимий рядок?
- ✓Правильна відповідь: Бінарним пошуком по накопичених зсувах рядків
- 2Проходом рядків зверху при кожному скролі
- 3Діленням scrollTop на середню висоту рядка
Пояснення
Префіксні суми висот рядків відсортовані, тож бінарний пошук знаходить рядок на scrollTop за O(log n). Прохід - O(n) на кожен скрол; ділення на середнє з'їжджає, коли висоти різні.