Binary Search vs Array.includes() on a 50,000-Row Catalog

Описание и применение

Замена Array.includes() на бинарный поиск в массиве из 50 000 элементов сократила время поиска с 408 мс до менее 1 мс, устранив заметную задержку в UI.

Задача

Searching large sorted arrays with Array.includes() is slow compared to binary search, causing noticeable UI delays.

Результат

Binary search outperformed Array.includes() by 432× for 10,000 lookups on 50,000 rows, turning a 408 ms delay into sub‑1 ms latency.

Рабочий процесс

• 1. Build a sorted array of 50,000 numbers.
• 2. Generate 2,000 lookup targets (80 % hits, 20 % misses).
• 3. Run Array.includes() for each target and time the total.
• 4. Run a binarySearch function for each target and time the total.
• 5. Compare timings and verify hit counts match.
• 6. If binary search is faster, replace includes() with binarySearch in the codebase.
• 7. Add a unit test covering edge cases (empty array, single item, out‑of‑range targets).

Доказательства

Array.includes() took 408ms for 10,000 lookups against 50,000 rows, binary search took under 1ms

Источник

Binary search needs a sorted array, so an unsorted catalog has to pay a one-time sort cost first

Источник

A one-line swap cut a 408ms lookup loop to under 1ms with zero new dependencies

Источник