Скорость поиска по массивам данных

Вопрос-ответ JavaScript
1

Есть такой код:

(function (app) {
	'use strict';

	var veryBigArray = [], i = 0;

	while (veryBigArray.length < 20000000) {
		veryBigArray.push(i+=2);
	}

	function quickSearch (searchElement) {
		return veryBigArray.indexOf(searchElement);
	}

	app.quickSearch = quickSearch;

})(window);

Для наглядного просмотра времени поиска индекса нужного значения в консоли пишем:

console.time('search1');
console.log(quickSearch(19999998));
console.timeEnd('search1');

Получаем примерный результат:

9999998
search1: 64.187ms

Вопрос: Какие алгоритмы вы используете(использовали бы) для ускорения поиска и уменьшения значения search1?

2

Для сортированных массивов - метод деления пополам https://ru.wikipedia.org/wiki/Двоичный_поиск

1 лайк
3

Попробовал создать еще одну структуру данных, где ключами были бы значения, а значениями - индексы значений. Корректно такой подход будет работать в ограниченном количестве случаев (когда значения - примитивы, и значения не дублируются).