Задача поиска элемента в массиве стоит перед всеми достаточно часто и хорошо бы расписать, как это можно сделать.

Ищут обычно в массиве элементы типа Number , String или Object . Естественно, самый быстрый способ поиска - по элементам типа Number , сравнение числа, даже очень большого, происходит очень быстро, гораздо проще проверить один элемент, чем лексиграфически сравнивать строки, а с объектами вообще другая история. Если мы ищем именно тот объект, который мы добавили в массив, то есть сравниваем ссылки - это так же быстро, как и сравнивать числа, а вот если же надо искать по свойствам объекта, то это может весьма и весьма затянуться. В особо сложных случаях, советую составлять какой-нибудь хэш объекта и строить отдельным массив-карту, в которой уже спокойно искать всё, что надо найти.

Разберем 6 способов сделать это на нативном JS разной новизны и 3 способа с их разбором на популярных фреймворках: jQuery , underscore и lodash .

Часть первая, нативная, в стиле аллегро

Для начала надо пройтись по родным возможностям языка и посмотреть, что можно сделать самим.

Поиск в лоб

Попробуем просто идти по элементам массива, пока мы не встретим то, что нам нужно. Как всегда самое простое решение является в среднем самым быстрым.

Function contains(arr, elem) { for (var i = 0; i < arr.length; i++) { if (arr[i] === elem) { return true; } } return false; }

Работает везде. Сравнивает строго, с помощью === . Легко можно заменить на == , бывает полезно, когда элементы массива разных типов, но может замедлить поиск. Его можно и модифицировать, добавив возможность начинать поиск элемента с конца. Шикарно ищет цифры, строки. Немного расширив, можно добавить возможность поиска элемента по своему условию (это поможет нам искать по свойствам объекта или, например, первый элемент, который больше 100500):

Function contains(arr, pred) { for (var i = 0; i < arr.length; i++) { if (typeof pred == "function" && pred(arr[i], i, arr) || arr[i] === elem) { return true; } } return false; }

Array.prototype.indexOf()

Array.prototype.indexOf(searchElement[, fromIndex = 0]) - старый добрый метод, заставляющий всех мучиться со своей -1 в случае, когда элемента нет.

Function contains(arr, elem) { return arr.indexOf(elem) != -1; }

Поддерживается он везде, кроме IE <= 7, но это уже давно забытая шутка. Данный метод выполняет поиск элемента строго от меньшего индекса к большему, применяя при сравнении === . Увы, по свойствам объекта мы так искать не сможем. arr.indexOf(searchElement, fromIndex) принимает два аргумента, первый searchElement - это элемент который ищем, а второй, fromIndex , индекс с которого начнем искать (отрицательный говорит интерпретатору начинать поиск с arr.length + fromIndex индекса). Аккуратней, если вы укажете fromIndex больше длины массива, метод нераздумывая вернёт -1 .

Function contains(arr, elem, from) { return arr.indexOf(elem, from) != -1; }

Array.prototype.lastIndexOf()

Array.prototype.lastIndexOf(searchElement[, fromIndex = arr.length - 1]) - справедливости ради надо рассказать и про него. Работает полностью аналогично Array.prototype.indexOf() , но только полностью наоборот (поиск идет в обратном порядке и fromIndex изначально отсчитывается с конца). Заменил конструкцию ret != -1 на!!~ret ради забавы.

Function contains(arr, elem, from) { return !!~arr.lastIndexOf(elem, from); }

Array.prototype.find()

Array.prototype.find(callback[, thisArg]) - модный стильный и молодежный ES6, со всеми вытекающими:

Function contains(arr, elem) { return arr.find((i) => i === elem) != -1; }

Возвращает элемент или -1 , если ничего не найдено. Ищет с помощью callback(elem, index, arr) , то есть, если эта функция вернет true , то это именно тот самый, искомый элемент. Конечно, эту функцию можно задавать самому, поэтому метод универсален.

Array.prototype.findIndex()

Array.prototype.findIndex(callback[, thisArg]) - полностью аналогичный предыдущему метод, за исключением того, что функция возвращает не элемент, а индекс. Забавы ради сделаю её с возможностью передать свою функцию:

Function contains(arr, pred) { var f = typeof pred == "function" ? pred: (i => i === pred); return arr.findIndex(f) != -1; }

Array.prototype.includes()

Array.prototype.includes(searchElement[, fromIndex]) - а это уже ES7, с ещё пока оочень сырой поддержкой. Наконец-то у нас будет специальный метод, чтобы узнать, есть ли элемент в массиве! Поздравляю!

Arr.includes(elem);

Это всё, что нужно, чтобы найти элемент. Аргументы у этой функции полностью аналогичны Array.prototype.indexOf() . А вот вернет он true в случае успеха и false в обратном. Естественно искать по свойствам объектов нельзя, для этого есть Array.prototype.find() . Должен быть самым быстрым, но... Возможно, что он и станет со временем самым быстрым.

Часть вторая, со вниманием, но чужая и в стиле сонаты

Теперь, наконец, можно поговорить об этой же теме, но в контексте парочки фреймворков! Говорят, что всегда хорошо посмотреть сначала, как делают другие, перед тем, как начнешь делать это сам. Может это откроет нам глаза на что-нибудь интересное!

jQuery

jQuery.inArray(value, array [, fromIndex ]) - между прочим весьма быстрый метод, по тестам.

Использует внутри строгое равенство === и возвращает -1 , если ничего не нашел, а если все таки нашёл, то вернет его индекс. Для удобства и одинаковости обернем её в функцию:

Function contains(arr, elem) { return jQuery.inArray(elem, arr) != -1; }

А теперь поговорим, как она работает. Вот, что она представляет из себя в версии 2.1.3:

InArray: function(elem, arr, i) { return arr == null ? -1: indexOf.call(arr, elem, i); }

Где indexOf это вот это:

// Use a stripped-down indexOf as it"s faster than native // http://jsperf.com/thor-indexof-vs-for/5 indexOf = function(list, elem) { var i = 0, len = list.length; for (; i < len; i++) { if (list[i] === elem) { return i; } } return -1; }

Забавный комментарий говорит, что так быстрее, чем родной Array.prototype.indexOf() (могу предположить, что из-за отсутствия всех проверок) и предлагает посмотреть тесты производительности.

По сути - это самый первый способ из первой части.

Underscore

_.contains(list, value) - вот такой метод предлагает нам популярная библиотека для работы с коллекциями. То же самое, что и _.include(list, value) .

Использует === для сравнения. Вернёт true , если в list содержится элемент, который мы ищем. Если list является массивом, будет вызван метод indexOf.

Contains = _.include = function(obj, target) { if (obj == null) return false; if (nativeIndexOf && obj.indexOf === nativeIndexOf) return obj.indexOf(target) != -1; return any(obj, function(value) { return value === target; }); };

Где nativeIndexOf - штука, которая говорит, что Array.prototype.indexOf() существует, а obj.indexOf === nativeIndexOf говорит, что list - массив. Теперь понятно, почему этот метод медленнее, чем jQuery.inArray() , просто обертка над Array.prototype.indexOf() . Ничего интересного.

Lodash

_.includes(collection, target, ) - вот последняя надежда на новые мысли, от второй знаменитейшей библиотеки для работы с коллекциями. То же самое, что _.contains() и _.include() .

Возвращает true , если содержит и false если нет. fromIndex индекс элемента, с которого начинаем поиск.

Function includes(collection, target, fromIndex, guard) { var length = collection ? getLength(collection) : 0; if (!isLength(length)) { collection = values(collection); length = collection.length; } if (typeof fromIndex != "number" || (guard && isIterateeCall(target, fromIndex, guard))) { fromIndex = 0; } else { fromIndex = fromIndex < 0 ? nativeMax(length + fromIndex, 0) : (fromIndex || 0); } return (typeof collection == "string" || !isArray(collection) && isString(collection)) ? (fromIndex <= length && collection.indexOf(target, fromIndex) > -1) : (!!length && getIndexOf(collection, target, fromIndex) > -1); }

guard - служебный аргумент. Сначала находится длина коллекции, выбирается fromIndex , а потом... нет, не Array.prototype.indexOf() ! Для поиска в строке используется String.prototype.indexOf() , а мы идем дальше в _.getIndexOf() и в результате попадём в ло-дашскую имплементацию indexOf() :

Function indexOf(array, value, fromIndex) { var length = array ? array.length: 0; if (!length) { return -1; } if (typeof fromIndex == "number") { fromIndex = fromIndex < 0 ? nativeMax(length + fromIndex, 0) : fromIndex; } else if (fromIndex) { var index = binaryIndex(array, value); if (index < length && (value === value ? (value === array) : (array !== array))) { return index; } return -1; } return baseIndexOf(array, value, fromIndex || 0); }

Она интересна тем, что fromIndex может принимать значения как Number , так и Boolean и если это всё таки значение булевого типа и оно равно true , то функция будет использовать бинарный поиск по массиву! Прикольно. Иначе же выполнится indexOf() попроще:

Function baseIndexOf(array, value, fromIndex) { if (value !== value) { return indexOfNaN(array, fromIndex); } var index = fromIndex - 1, length = array.length; while (++index < length) { if (array === value) { return index; } } return -1; }

Интересный ход для случая, когда мы ищем NaN (напомню, что из-за досадной ошибки он не равен сам себе). Выполнится indexOfNaN() , и действительно ни один из всех способов описанных ранее не смог бы найти NaN , кроме тех, естественно, где мы могли сами указать функцию для отбора элементов.

Можно предложить просто обернуть _.indexOf() для поиска элемента:

Function contains(arr, elem, fromIndex) { return _.indexOf(arr, elem, fromIndex) != -1; }

Где fromIndex будет либо индексом откуда начинаем искать, либо true , если мы знаем, что arr отсортирован.

Заключение, хотя и в стиле интермеццо

И да, все эти варианты имеют смысл, только если момент с поиском данных част в вашем алгоритме или поиск происходит на очень больших данных. Вот приведу ниже несколько тестов на поиск элементов типа Number и String в массивах длинной 1000000 (миллион) элементов для трех случаев, когда элемент находится вначале массива, в середине (можно считать за среднюю по палете ситуацию) и в конце (можно считать за время поиска отсутствующего элемента, кроме метода с Array.prototype.lastIndexOf()).

The indexOf() method returns the first index at which a given element can be found in the array, or -1 if it is not present.

The source for this interactive example is stored in a GitHub repository. If you"d like to contribute to the interactive examples project, please clone https://github.com/mdn/interactive-examples and send us a pull request.

Syntax

arr .indexOf(searchElement[ , fromIndex])

Parameters

searchElement Element to locate in the array. fromIndex Optional The index to start the search at. If the index is greater than or equal to the array"s length, -1 is returned, which means the array will not be searched. If the provided index value is a negative number, it is taken as the offset from the end of the array. Note: if the provided index is negative, the array is still searched from front to back. If the provided index is 0, then the whole array will be searched. Default: 0 (entire array is searched).

Return value

The first index of the element in the array; -1 if not found.

Description

indexOf() compares searchElement to elements of the Array using strict equality (the same method used by the === or triple-equals operator).

Examples

Using indexOf()

The following example uses indexOf() to locate values in an array.

Var array = ; array.indexOf(2); // 0 array.indexOf(7); // -1 array.indexOf(9, 2); // 2 array.indexOf(2, -1); // -1 array.indexOf(2, -3); // 0

Finding all the occurrences of an element

var indices = ; var array = ["a", "b", "a", "c", "a", "d"]; var element = "a"; var idx = array.indexOf(element); while (idx != -1) { indices.push(idx); idx = array.indexOf(element, idx + 1); } console.log(indices); //

Finding if an element exists in the array or not and updating the array

Polyfill

indexOf() was added to the ECMA-262 standard in the 5th edition; as such it may not be present in all browsers. You can work around this by utilizing the following code at the beginning of your scripts. This will allow you to use indexOf() when there is still no native support. This algorithm matches the one specified in ECMA-262, 5th edition, assuming TypeError and Math.abs() have their original values.

If (!Array.prototype.indexOf) Array.prototype.indexOf = (function(Object, max, min){ "use strict"; return function indexOf(member, fromIndex) { if(this===null||this===undefined)throw TypeError("Array.prototype.indexOf called on null or undefined"); var that = Object(this), Len = that.length >>> 0, i = min(fromIndex | 0, Len); if (i < 0) i = max(0, Len+i); else if (i >= Len) return -1; if(member===void 0){ for(; i !== Len; ++i) if(that[i]===void 0 && i in that) return i; // undefined }else if(member !== member){ for(; i !== Len; ++i) if(that[i] !== that[i]) return i; // NaN }else for(; i !== Len; ++i) if(that[i] === member) return i; // all else return -1; // if the value was not found, then return -1 }; })(Object, Math.max, Math.min);

However, if you are more interested in all the little technical bits defined by the ECMA standard, and are less concerned about performance or conciseness, then you may find this more descriptive polyfill to be more useful.

// Production steps of ECMA-262, Edition 5, 15.4.4.14 // Reference: http://es5.github.io/#x15.4.4.14 if (!Array.prototype.indexOf) { Array.prototype.indexOf = function(searchElement, fromIndex) { var k; // 1. Let o be the result of calling ToObject passing // the this value as the argument. if (this == null) { throw new TypeError(""this" is null or not defined"); } var o = Object(this); // 2. Let lenValue be the result of calling the Get // internal method of o with the argument "length". // 3. Let len be ToUint32(lenValue). var len = o.length >>> 0; // 4. If len is 0, return -1. if (len === 0) { return -1; } // 5. If argument fromIndex was passed let n be // ToInteger(fromIndex); else let n be 0. var n = fromIndex | 0; // 6. If n >= len, return -1. if (n >= len) { return -1; } // 7. If n >= 0, then Let k be n. // 8. Else, n<0, Let k be len - abs(n). // If k is less than 0, then let k be 0. k = Math.max(n >= 0 ? n: len - Math.abs(n), 0); // 9. Repeat, while k < len while (k < len) { // a. Let Pk be ToString(k). // This is implicit for LHS operands of the in operator // b. Let kPresent be the result of calling the // HasProperty internal method of o with argument Pk. // This step can be combined with c // c. If kPresent is true, then // i. Let elementK be the result of calling the Get // internal method of o with the argument ToString(k). // ii. Let same be the result of applying the // Strict Equality Comparison Algorithm to // searchElement and elementK. // iii. If same is true, return k. if (k in o && o[k] === searchElement) { return k; } k++; } return -1; }; }

Specifications

Specification	Status	Comment
ECMAScript 5.1 (ECMA-262)	Standard	Initial definition. Implemented in JavaScript 1.6.
ECMAScript 2015 (6th Edition, ECMA-262) The definition of "Array.prototype.indexOf" in that specification.	Standard
ECMAScript Latest Draft (ECMA-262) The definition of "Array.prototype.indexOf" in that specification.	Draft

Browser compatibility

The compatibility table in this page is generated from structured data. If you"d like to contribute to the data, please check out https://github.com/mdn/browser-compat-data and send us a pull request.

Update compatibility data on GitHub

	Desktop						Mobile							Server
	Chrome	Edge	Firefox	Internet Explorer	Opera	Safari	Android webview	Chrome for Android	Edge Mobile	Firefox for Android	Opera for Android	Safari on iOS	Samsung Internet	Node.js
Basic support	Chrome Full support Yes	Edge Full support Yes	Firefox Full support 1.5	IE Full support 9	Opera Full support Yes	Safari Full support Yes	WebView Android Full support Yes	Chrome Android Full support Yes	Edge Mobile Full support Yes	Firefox Android Full support 4	Opera Android Full support Yes	Safari iOS Full support Yes	Samsung Internet Android Full support Yes	nodejs Full support Yes

Legend

Full support Full support

Compatibility notes

Starting with Firefox 47 (Firefox 47 / Thunderbird 47 / SeaMonkey 2.44), this method will no longer return -0 . For example, .indexOf(0, -0) will now always return +0 (

Прежде всего, существует некоторая фундаментальная путаница в том, какие структуры данных доступны в JavaScript.

JavaScript не имеет массивов

По сути, JavaScript имеет только хеш-таблицы. Стандартная функция Array строит хэш-таблицы (я буду называть эти целые хэш-таблицы или int-hash-tables ), где ключи являются целыми числами в дополнение к строковым клавишам. Они работают аналогично массивам, но они различаются определенным образом. Есть минусы и профи. Например, удаление элемента из int-hash-table является операцией O (1), а удаление элемента из массива - это операция O (n) (потому что вам нужно скопировать остальные элементы в новый массив). Вот почему функция Array.prototype.splice в JavaScript очень быстро. Недостатком является сложность реализации.

Итак, когда вы говорите Array в контексте JavaScript, это понимается как int-hash-table и вся связанная с ним асимптотическая сложность. Это означает, что если вы хотите найти строковое значение внутри таблицы int-hash, то это будет операция O (n). Для этого есть стандартная функция: Array.prototype.indexOf . Однако, если вы хотите найти ключ , то есть две функции: in и Object.prototype.hasOwnProperty .

Несколько противоречиво:

[ 1 , 2 , 3 ]. hasOwnProperty (0 ); // true 0 in [ 1 , 2 , 3 ]; // true

Разница между этими двумя требует дальнейшего объяснения. Это связано с тем, что все объекты в JavaScript являются объектами и, следовательно, имеют некоторые объекты-y. Один из них показывает prototype , связь между объектом и его прототипом. Это иерархическая структура хеш-таблиц, каждая из которых содержит свойства объектов.

in поисках немедленной хеш-таблицы объекта, а затем рекурсивно ищет хеш-таблицы прототипов этих объектов.

В то время как Object.prototype.hasOwnProperty только просматривает непосредственную хеш-таблицу. Вы можете подумать, что это должно быть быстрее, но подождите, пока вы не перейдете к выводам.

Из-за динамического характера JavaScript все вызовы функций динамичны, и среда должна заботиться о том, чтобы обеспечить выполнение отказобезопасного кода. Это означает, что вызовы функций JavaScript очень дороги. Итак, переход через Object.prototype.hasOwnProperty может быть намного дороже, чем проходить, хотя теоретически это должно быть наоборот. Однако, учитывая достаточно высокое дерево наследования и достаточное количество унаследованных свойств, в конечном итоге, Object.prototype.hasOwnProperty возьмет верх.

Некоторые примеры для лучшей интуиции:

>>> var array = [ 1 , 2 , 3 ]; undefined >>> 3 in array ; false >>> array . hasOwnProperty (3 ); false >>> 3 in array ; false >>> array . __proto__ = [ 1 , 2 , 3 , 4 ]; [ 1 , 2 , 3 , 4 ] >>> 3 in array ; true >>> array . hasOwnProperty (3 ); false

Если вам нужен быстрый поиск ключей для объектов с короткой цепочкой наследования прототипов, используйте.

Если вы хотите то же самое, но для объектов с обширной цепочкой наследования, используйте Object.prototype.hasOnwProperty

Если вам нужен быстрый поиск, используйте Array.prototype.indexOf для Array .

В хэш-таблицах нет встроенной функции для поиска значений. Вы можете, конечно, сворачивать свои собственные, но есть много библиотек, которые уже предоставляют их. Например, Underscore предоставляет один (он называет его indexOf).