Как быстро найти элемент в массиве

Маленькая интродукция

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

Ищут обычно в массиве элементы типа 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, [fromIndex=0]) – вот последняя надежда на новые мысли, от второй знаменитейшей библиотеки для работы с коллекциями. То же самое, что _.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[index]) : (array[index] !== array[index]))) {
            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[index] === 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()).

1. Number, 1000000 элементов, искомый элемент в начале;
2. Number, 1000000 элементов, искомый элемент в середине;
3. Number, 1000000 элементов, искомый элемент в конце;
4. String, 1000000 элементов, искомый элемент в начале;
5. String, 1000000 элементов, искомый элемент в середине;
6. String, 1000000 элементов, искомый элемент в конце.

Результаты тестов могут сильно зависеть от версии браузера, да и от самих браузеров, как этого избежать не знаю, но рекомендую протестить на нескольких.

Видно, что в среднем везде выигрывает первый способ из первой части (написанный собственноручно), а второе место обычно делят lоdash и Array.prototype.includes().

Да, прошу заметить, что если взбредёт в голову искать NaN, то это может не получиться почти во всех методах, так как NaN !== NaN.

• Главная

• Инструкции

• JavaScript

• Методы поиска в массивах JavaScript

Поиск в массиве — довольно несложная задача для программиста. На ум сразу приходит перебор через цикл for или бинарный поиск в отсортированном массиве, для элементов которого определены операции «больше» и «меньше». Но, как и любой высокоуровневый язык программирования, JavaScript предлагает разработчику встроенные функции для решения различных задач. В этой статье мы рассмотрим четыре метода поиска в массивах JavaScript: find, includes, indexOf и filter.

indexOf

indexOf — это функция поиска элемента в массиве. Этот метод с помощью перебора ищет искомый объект и возвращает его индекс или “-1”, если не находит подходящий.

Синтаксис

Функция имеет такой синтаксис:

Array.indexOf (search element, starting index)

где:

• Array — массив;
• search element — элемент, который мы ищем;
• starting index — индекс, с которого начинаем перебор. Необязательный аргумент, по умолчанию работа функции начинается с индекса “0”, т.е. метод проверяет весь Array. Если starting index больше или равен Array.length, то метод сразу возвращает “-1” и завершает работу. 

Если starting index отрицательный, то JS трактует это как смещение с конца  массива: при starting index = “-1” будет проверен только последний элемент, при “-2” последние два и т.д. 

Практика

Опробуем метод на практике. Запустим такой код и проверим результаты его работы:

let ExampleArray = [1,2,3,1,'5', null, false, NaN,3];
console.log("Позиция единицы", ExampleArray.indexOf(1) );
console.log("Позиция следующей единицы", ExampleArray.indexOf(1,2) );
console.log("Позиция тройки", ExampleArray.indexOf(3) );
console.log("Позиция тройки, если starting index отрицательный", ExampleArray.indexOf(3,-2) );
console.log("Позиция false", ExampleArray.indexOf(false) );
console.log("Позиция 5", ExampleArray.indexOf("5") ); 
console.log("Позиция NaN", ExampleArray.indexOf(NaN));

В результате работы этого кода мы получили такой вывод: 

Позиция единицы 0
Позиция следующей единицы 3
Позиция тройки 2
Позиция тройки, если starting index отрицательный 8
Позиция false 6
Позиция 5 -1
Позиция NaN -1

indexOf осуществляет поиск элемента в массиве слева направо и останавливает свою работу на первом совпавшем. Отчетливо это проявляется в примере с единицей. Для того, чтобы идти справа налево, используйте метод LastIndexOf с аналогичным синтаксисом.

Для сравнения искомого и очередного объекта применяется строгое сравнение (===). При использовании строгого сравнения для разных типов данных, но с одинаковым значение, например 5, ‘5’ и “5” JavaScript даёт отрицательный результат, поэтому IndexOf не нашел 5. 

Также стоит помнить, что indexOf некорректно обрабатывает NaN. Так что для работы с этим значением нужно применять остальные методы.

includes

includes не совсем проводит поиск заданного элемента в массиве, а проверяет, есть ли он там вообще. Работает он примерно также как и indexOf. В конце работы includes возвращает «True», если нашел искомый объект, и «False», если нет. Также includes правильно обрабатывает NaN

Синтаксис

includes имеет следующий синтаксис:

Array.includes (search element, starting index)

где: 

• Array — массив;
• search element — элемент, который мы ищем;
• starting index — индекс, с которого начинаем перебор. Необязательный аргумент, по умолчанию работа функции начинается с индекса “0”, т.е. метод проверяет весь Array. Если starting index больше или равен Array.length, то метод сразу возвращает «False» и завершает работу.  

Если starting index отрицательный, то JS трактует это как смещение с конца массива: при starting index = “-1” будет проверен только последний элемент, при “-2” последние два и т.д.  

Практика

Немного изменим код из предыдущего примера и запустим его:

let Example = [1,2,3,1,'5', null, false,NaN, 3];
console.log("Наличие единицы", Example.includes(1) );
console.log("Наличие следующей единицы", Example.includes(1,2) );
console.log("Наличие тройки", Example.includes(3) );
console.log("Наличие тройки, если starting index отрицательный", Example.includes(3,-1) );
console.log("Наличие false", Example.includes(false) );
console.log("Наличие 5", Example.includes(5) ); 
console.log("Наличие NaN", Example.includes(NaN));

Вывод:

Наличие единицы true
Наличие следующей единицы true
Наличие тройки true
Наличие тройки, если starting index отрицательный true
Наличие false true
Наличие 5 false
Наличие NaN true

Для includes отсутствует альтернативная функция, которая проводит поиск по массиву js справа налево, которая, в общем-то, и не очень актуальна.

find

Предположим, что нам нужно найти в массиве некий объект. Но мы хотим найти его не по значению, а по его свойству. Например, поиск числа в массиве со значением между 15 и 20. Как и прежде, мы можем воспользоваться перебором с помощью for, но это не слишком удобно. Для поиска с определенным условием в JavaScript существует метод find.

Синтаксис

Array.find(function(...){
//если элемент соответствует условиям (true), то функция возвращает его  и прекращает работу;
//если ничего не найдено, то возвращает undefined
})

• Array — массив;
• function(…) — функция, которая задает условия.

Практика

Как и в прошлых примерах, напишем небольшой код и опробуем метод:

let ExampleArray = ["Timeweb", 55555, "Cloud", "облачный провайдер", "буквы"];
console.log(ExampleArray.find(element => element.length == 5))

Вывод:

Cloud

В этом примере мы искали строки с длиной в 5 символов. Для числовых типов данных длина не определена, поэтому 55555 не подходит. find находит первый элемент и возвращает его, поэтому «буквы» также не попали в результат работы нашей функции. Для того, чтобы найти несколько элементов, соответствующих некоторому условию, нужно использовать метод filter.

Также не стоит забывать о методе findIndex. Он возвращает индекс подходящего элемента. Или -1, если его нет. В остальном он работает точно также, как и find.

filter

find ищет и возвращает первый попавшийся элемент, соответствующий условиям поиска. Для того, чтобы найти все такие элементы, необходимо использовать метод filter. Результат этой функции — массив (если ничего не найдено, то он будет пустым).

Синтаксис

Array.find(function(...){
//если элемент соответствует условиям (true), то добавляем его к конечному результату и продолжаем перебор;
})

• Array — массив;
• function(…) — функция, которая задает условия.

Практика

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

let ExampleArray = [
  [10, 15, 8],
  [11, 12, 6],
  [5, 20, 1],
  [10, 10, 2],
  [16,2, 4]
  ];
console.log(ExampleArray.filter(element=> element[0]*element[1]*element[2]>300))

 Вывод:

[ [ 10, 15, 8 ],
 [ 11, 12, 6 ] ]

В этом примере мы нашли прямоугольные параллелепипеды с объемом больше 300. В целом, метод filter в JS позволяет реализовывать всевозможные условия для поиска. 

Заключение

В этой статье узнали о методах поиска в JavaScript и научились ими пользоваться. Все перечисленные методы — универсальные инструменты для разработчиков. Но, как и любые универсальные инструменты, они не всегда являются самыми производительными. Так, например, бинарный поиск будет куда эффективнее, чем find и filter.

Для поиска по массиву в JavaScript существует несколько методов прототипа Array, не считая что поиск можно выполнить и методами для перебора массива и в обычном цикле.

Итак, мы сегодня рассмотрим следующие варианты:

• Array.includes()
• Array.indexOf()
• Array.find()
• Array.findIndex()
• Array.filter()
• Array.forEach()

Array.includes() — есть ли элемент в массиве

Данный метод ищет заданный элемент и возвращает true или false, в зависимости от результата поиска. Принимает два параметра:

• element — то, что мы будем искать
• fromIndex (необязательный) — с какого индекса начинать поиск. По умолчанию с 0.

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry'];

console.log(arr.includes('Apple')); // true
console.log(arr.includes('Apple', 1)); // false

Как видно из примера выше, в первом случае мы получим true, т.к. начали с нулевого элемента массива. Во втором случае мы передали второй параметр — индекс, с которого нужно начать поиск — и получили false, т.к. дальше элемент не был найден.

Array.indexOf() — индекс элемента в массиве

Данный метод, в отличие от предыдущего, возвращает индекс первого найденного совпадения. В случае если элемент не найден, будет возвращено число -1

Также принимает два параметра:

• element — элемент, который мы будем искать
• fromIndex (необязательный) — с какого индекса начинать поиск. По умолчанию с 0.

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

console.log(arr.indexOf('Apple')); // 0
console.log(arr.indexOf('Apple', 1)); // 4
console.log(arr.indexOf('Orange', 2)); // -1

Как видно из примера выше, в первом случае мы получаем 0, т.к. сразу нашли первый элемент массива (первое совпадение, дальше поиск уже не выполняется). Во втором случае 4, т.к. начали поиск с индекса 1 и нашли следующее совпадение. В третьем примере мы получили результат -1, т.к. поиск начали с индекса 2, а элемент Orange в нашем массиве под индексом 1.

Так как данный метод возвращает индекс или -1, мы можем присвоить результат в переменную для дальнейшего использования:

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];
const index = arr.indexOf('Lemon');

if (index !== -1) {
    // сделать что-то
}

Чтобы произвести какие-то действия над найденным элементом массива, мы можем использовать следующий синтаксис:

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];
const index = arr.indexOf('Lemon');

arr[index] = 'Lime'; // заменяем найденный элемент
console.log(arr)ж // ['Apple', 'Orange', 'Lime', 'Cherry', 'Apple']

Примеры использования данного метода вы можете также найти в посте про удаление элемента из массива

Array.find() — найти элемент по условию

Данный метод callback и thisArg в качестве аргументов и возвращает первое найденное значение.

Callback принимает несколько аргументов:
item — текущий элемент массива
index — индекс текущего элемента
currentArray — итерируемый массив

Пример использования:

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];
  
const apple = arr.find(item => item === 'Apple');

console.log(apple); // Apple

Данный метод полезен тем, что мы можем найти и получить сразу и искомый элемент, и его index

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

let indexOfEl;
const apple = arr.find((item, index) => {
  if (item === 'Apple') {
    indexOfEl = index;
    return item;
  }
});

console.log(apple, indexOfEl); // Apple 0

Также работа кода прекратиться как только будет найден нужный элемент и второй элемент (дубликат) не будет найден.

В случае если ничего не найдено будет возвращен undefined.

Array.findIndex() — найти индекс элемента в массиве

Этот метод похож на метод find(), но возвращать будет только индекс элемента, который соответствует требованию. В случае, если ничего не найдено, вернет -1

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

const index = arr.findIndex(item => item === 'Apple');

console.log(index); // 0

Ну и по аналогии с предыдущим методом, поиск завершается после первого совпадения.

Поиск всех совпадений в массиве

Метод filter() кроме всего остального также можно использовать для поиска по массиву. Предыдущие методы останавливаются при первом соответствии поиска, а данный метод пройдется по массиву до конца и найдет все элементы. Но данный метод вернет новый массив, в который войдут все элементы соответствующие условию.

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

const filteredArr = arr.filter(item => item === 'Apple');

console.log(filteredArr); // ['Apple', 'Apple']
console.log(arr); // ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

Как видите из примера выше, первоначальный массив не будет изменен.

Подробнее про метод JS filter() можете прочитать в этом посте.

Для этих же целей можно использовать метод forEach(), который предназначен для перебора по массиву:

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

let indexes = [];
arr.forEach((item, index) => {
  if (item === 'Apple') indexes.push(index)
});

console.log(indexes); // [0, 4]

В массив indexes мы получили индексы найденных элементов, это 0 и 4 элементы. Также в зависимости от вашей необходимости, можно создать объект, где ключом будет индекс, а значением сам элемент:

const arr = ['Apple', 'Orange', 'Lemon', 'Cherry', 'Apple'];

let arrObjMap = {};
arr.forEach((item, index) => {
  if (item === 'Apple') {
    arrObjMap[index] = item;
  }
});

console.log(arrObjMap); // {0: 'Apple', 4: 'Apple'}

Поиск в массиве объектов

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

Первый способ. С использованием метода map для массива

const arr = [
    { name: 'Ben', age: 21 },
    { name: 'Clif', age: 22 },
    { name: 'Eric', age: 18 },
    { name: 'Anna', age: 27 },
];

const index = arr.map(item => item.name).indexOf('Anna');


console.log(index); //3
console.log(arr[index]); // {name: 'Anna', age: 27}

В данном случае по массиву arr мы проходим и на каждой итерации из текущего элемента (а это объект со свойствами name и age) возвращаем имя человека в новый массив и сразу же выполняем поиск по новому массиву на имя Anna. При совпадении нам будет возвращен индекс искомого элемента в массиве.

Второй способ. Данный вариант будет немного проще, т.к. мы можем сразу получить индекс при совпадении:

const index = arr.findIndex(item => item.name === 'Anna');

console.log(index); //3
console.log(arr[index]); // {name: 'Anna', age: 27}

Заключение

Как видите любой из вышеприведенных методов можно использовать для поиска по массиву. Какой из них использовать зависит от вашей задачи и того, что вам нужно получить — сам элемент или его индекс в массиве, найти только первое совпадение или все совпадения при поиске.

Ваши вопросы и комментарии:

Целочисленный двоичный поиск (бинарный поиск) (англ. binary search) — алгоритм поиска объекта по заданному признаку в множестве объектов, упорядоченных по тому же самому признаку, работающий за логарифмическое время.

Принцип работы

Двоичный поиск заключается в том, что на каждом шаге множество объектов делится на две части и в работе остаётся та часть множества, где находится искомый объект. Или же, в зависимости от постановки задачи, мы можем остановить процесс, когда мы получим первый или же последний индекс вхождения элемента. Последнее условие — это левосторонний/правосторонний двоичный поиск.

Правосторонний/левосторонний целочисленный двоичный поиск

Для простоты дальнейших определений будем считать, что и что (массив нумеруется с ).

Использовав эти два вида двоичного поиска, мы можем найти отрезок позиций таких, что и

Пример:

Задан отсортированный массив .

Правосторонний поиск двойки выдаст в результате , в то время как левосторонний выдаст (нумерация с нуля).

Отсюда следует, что количество подряд идущих двоек равно длине отрезка , то есть .

Если искомого элемента в массиве нет, то правосторонний поиск выдаст максимальный элемент, меньший искомого, а левосторонний наоборот, минимальный элемент, больший искомого.

Алгоритм двоичного поиска

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

Код

int binSearch(int[] a, int key):   // Запускаем бинарный поиск
    int l = -1                      // l, r — левая и правая границы
    int r = len(a)    
    while l < r - 1                // Запускаем цикл
        m = (l + r) / 2            // m — середина области поиска
        if a[m] < key
            l = m
        else 
            r = m                  // Сужение границ
    return r

Инвариант цикла: правый индекс не меньше искомого элемента, а левый — строго меньше (т.к значение присваевается левой границе , только тогда, когда строго меньше искомого элемента ), тогда если (что эквивалентно ), то понятно, что — самое левое вхождение искомого элемента (так как предыдущие элементы уже меньше искомого элемента)

В случае правостороннего поиска изменится знак сравнения при сужении границ на , а возвращаемой переменной станет .

Несколько слов об эвристиках

Эвристика с завершением поиска, при досрочном нахождении искомого элемента

Заметим, что если нам необходимо просто проверить наличие элемента в упорядоченном множестве, то можно использовать любой из правостороннего и левостороннего поиска.
При этом будем на каждой итерации проверять “не попали ли мы в элемент, равный искомому”, и в случае попадания заканчивать поиск.

Эвристика с запоминанием ответа на предыдущий запрос

Пусть дан отсортированный массив чисел, упорядоченных по неубыванию.
Также пусть запросы приходят в таком порядке, что каждый следующий не меньше, чем предыдущий.
Для ответа на запрос будем использовать левосторонний двоичный поиск.
При этом после того как обработался первый запрос, запомним чему равно , запишем его в переменную .
Когда будем обрабатывать следующий запрос, то проинициализируем левую границу как .
Заметим, что все элементы, которые лежат не правее , строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.

Применение двоичного поиска на некоторых неотсортированных массивах

Если массив, отсортированный по возрастанию, был циклически сдвинут, тогда полученный массив состоит из двух отсортированных частей. Используем двоичный поиск, чтобы найти индекс последнего элемента левой части массива. Для этого в реализации двоичного поиска заменим условие в if на , тогда в будет содержаться искомый индекс:



int l = -1
int r = len(a)   
while l < r - 1                // С помощью бинарного поиска найдем максимум на массиве
    m = (l + r) / 2            // m — середина области поиска
    if a[m] > a[n - 1]         // Сужение границ
        l = m
    else 
        r = m
int x = l                      // x — искомый индекс.

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



if key > a[0]               // Если key в левой части
    l = -1
    r = x + 1
if key < a[n]               // Если key в правой части
    l = x 
    r = n

Время выполнения данного алгоритма — .

Найдем индекс последнего элемента массива, отсортированного по возрастанию, воспользовавшись троичным поиском, затем запустим левосторонний двоичный поиск для каждого массива отдельно: для элементов и для элементов , где в качестве мы возьмем индекс максимума, найденный троичным поиском. Для массива, отсортированного по убыванию используем двоичный поиск, изменив условие в if на .

Время выполнения алгоритма — (так как и бинарный поиск, и тернарный поиск работают за логарифмическое время с точностью до константы).

Мы имеем массив, образованный из двух отсортированных подмассивов, записанных один в конец другого. Запустить сразу бинарный или тернарный поиски на таком массиве нельзя, так как массив не будет обязательно отсортированным и он не будет иметь точку экстремума. Поэтому попробуем найти индекс последнего элемента левого массива, чтобы потом запустить бинарный поиск два раза на отсортированных массивах.

Докажем, что найти этот индекс невозможно быстрее, чем за . Возьмем возрастающий массив целых чисел, начиная с . Он удовлетворяет условию задачи. Вставим в него на любую позицию. Такой массив по-прежнему будет удовлетворять условию задачи. Следовательно, из-за того, что может находиться на любой позиции, мы можем его найти лишь за .

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

Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке , а затем, в зависимости от того, что мы ищем, мы либо поднимаемся, либо опускаемся по этому промежутку возрастания (убывания). Однако при таком решении могут быть неправильно найдены значения минимума или максимума. Рассмотрим случаи, когда они будут неправильно найдены. Определить, какого вида наш массив возможно, сравнив первые два элемента массива.

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

В случае же убывание-возрастание-убывание () может быть, что будет неправильно найден минимум. Найдем правильный минимум аналогично поиску максимума в предыдущем абзаце.

Затем, в зависимости от типа нашего массива, запустим бинарный поиск три раза на каждом промежутке.

Время выполнения данного алгоритма — .

Переполнение индекса середины

В некоторых языках программирования присвоение m = (l + r) / 2 приводит к переполнению. Вместо этого рекомендуется использовать m = l + (r - l) / 2; или эквивалентные выражения.^[1]

См. также

• Вещественный двоичный поиск
• Троичный поиск
• Поиск с помощью золотого сечения
• Интерполяционный поиск

Источники информации

• Д. Кнут — Искусство программирования (Том 3, 2-е издание)
• Википедия — двоичный поиск
• Типичные ошибки при написании бинарного поиска
• Бинарный поиск на algolist

Примечания