Изучаем JavaScript: поиск в массиве с помощью методов indexOf и lastIndexOf
В статье рассказывается о том, как использовать методы JavaScript indexOf и lastIndexOf для определения расположения элемента внутри массива.
Поиск элемента в массиве — знакомство с методом indexOf
Чтобы определить расположение элемента в массиве, можно воспользоваться методом indexOf() . Он возвращает индекс первого вхождения элемента, либо -1 , если он не найден.
Ниже приведен синтаксис метода indexOf() :
Метод indexOf() принимает два аргумента. searchElement -это элемент, который нужно найти в массиве. fromIndex – это индекс массива, с которого нужно начать поиск.
Аргумент fromIndex в качестве значения может принимать как положительное, так и отрицательное целое число. Если значение аргумента fromIndex будет отрицательным, метод indexOf() начнет поиск по всему массиву плюс значение fromIndex . Если опустить аргумент fromIndex , то метод начнет поиск с элемента 0 .
Учтите, что метод JavaScript array indexOf() при сравнении searchElement с элементами в массиве, использует алгоритм строгого равенства , схожий с оператором “ тройное равно ” (===) .
Примеры применения метода indexOf()
Предположим, что есть массив scores , в котором содержится шесть чисел:
В следующем примере метод indexOf() используется для поиска элементов в массиве scores :
Бинарный поиск
Мы считаем, что вы уже знаете линейный поиск, а именно умеете решать задачи такого типа:
- Проверить, есть ли в массиве число X
- Найти максимум в массиве
- Найти сумму чисел в массиве
- Найти первое четное число в массиве
Все такие задачи решаются с помощью одного прохода по массиву с помощью цикла for. Все такие алгоритмы работают за \(O(n)\) . И даже можно понять, что быстрее, чем \(O(n)\) решить ни одну из этих задач не получится.
Задание
Убедитесь, что вы умеете решать эти задачи. Докажите, что быстрее, чем O(n) их решить в худшем случае нельзя.
Бинарный поиск
Однако иногда найти число X в массиве можно и быстрее! Для этого надо добавить условие на то, что массив отсортирован. Но давайте начнем не с этого.
Задание
Я загадал число X от 1 до 100. Вы можете спрашивать, больше ли мое число чем число T, я отвечаю “да” или “нет”. За сколько вопросов в худшем случае вы сможете найти число X? Как нужно действовать?
Решение и состоит в идее бинарного (двоичного) поиска — нужно первым вопросом спросить “число X больше, чем 50?”. После этого, если ответ “нет”, надо спросить “число X больше, чем 25”? И так далее, нужно уменьшать отрезок возможных значений в два раза каждый раз.
Почему нужно делить обязательно пополам? Почему бы не спросить “число X больше, чем 80?” первым же вопросом? Но если вдруг ответ “нет”, то мы останемся с 80 вариантами вместо 100. То есть деление отрезка ровно пополам гарантирует, что в худшем случае мы останемся не более чем с половиной вариантов.
Чтобы понять, как быстро это работает, введём новую математическую функцию. Логарифмом по основанию \(a\) от \(b\) будем называть число \(c\) , такое что \(a ^ c = b\) . Обозначается как \(\log_a b = c\) . Чаще всего мы будем работать с двоичным логарифмом, то есть в какую степень \(c\) нужно возвести двойку, чтобы получить \(b\) . Поэтому договоримся, что запись \(\log n\) означает двочный логарифм \(n\) .
Теперь вернёмся к нашей задаче. Можно понять, что такой алгоритм работает как раз за \(O(\log n)\) вопросов (если число 100 на заменить абстрактную переменную \(n\) ). Несложно убедиться, что именно логарифм раз нужно поделить число на два, чтобы получилось 1.
Общий принцип
А теперь представьте такую задачу: у вас есть массив, состоящий из некоторого количества подряд идущих нулей, за которыми следует какое-то количество подряд идущих единиц.
Вам дан массив, и вам нужно найти позицию первой единицы, то есть найти такое место, где заканчиваются нули, и начинаются единицы. Это можно сделать с помощью линейного поиска за один проход по массиву, но хочется сделать это быстрее.
Давайте обратимся к идее бинарного поиска. Посмотрим на элемент посередине массива. Если это нуль, то первую единицу стоит искать в правой половину массива, а если единица — то в левой.
Есть много способов писать бинарный поиск, и в его написании люди очень часто путаются. Очень удобно в данном случае воспользоваться инвариантом (это слово значит “постоянное свойство”):
Пусть переменная left всегда указывает на \(0\) в массиве, а переменная right всегда указывает на \(1\) в массиве.
Дальше мы будем переменные left и right постепенно сдвигать друг к другу, и в какой-то момент они станут соседними числами. Это и будет означать, что мы нашли место, где заканчиваются нули и начинаются единицы.
Чему равны left и right изначально, когда мы ничего про массив не знаем? Первая приходящая в голову идея — поставить их на \(0\) и \(n-1\) соответственно. Увы, в общем случае это может быть неверно, потому что a[0] может быть единицей, а a[n-1] может быть нулём. Правильнее сделать вот так:
То есть изначально left и right указывают на несуществующие индексы. Но это нормально — например в массиве [1, 1, 1, 1] в конце алгоритма как раз должно быть left == -1 , right == 0 .
Осталось нам написать цикл while :
Мы решили задачу для ноликов и единичек, но это легко обобщается на абсолютно любую задачу, где есть какое-то свойство, которое в начале массива не выполняется, а потом выполняется.
Например, если мы хотим найти, есть ли число \(X\) в отсортированном массиве, то мы просто представим, что \(0\) — это числа, меньшие \(X\) , а \(1\) — это числа, большие или равные \(X\) . Тогда достаточно найти первую “единицу” и проверить, равно ли это число \(X\) .
Задание
Придумайте, как с помощью бинарного поиска решить такие задачи: * Найти первое число, равное X в отсортированном массиве, или вывести, что таких чисел нет * Найти последнее число, равное X в отсортированном массиве, или вывести, что таких чисел нет * Посчитать, сколько раз встречается число X в отсортированном массиве (в решении помогают два предыдущих пункта) * Дан массив чисел, первая часть состоит из нечетных чисел, а вторая — из четных. Найти индекс, начиная с которого все числа четные.
Все эти задачи решаются бинарным поиском за \(O(\log
Поэтому зачастую такие задачи сформулированы таким образом:
Дан отсортированный массив размера \(n\) . Нужно ответить на \(m\) запросов вида “встречается ли число \(x_i\) в массиве n”?
Способы поиска элемента в массиве С: просто о сложном
Линейный поиск в массиве на С является самым простым алгоритмом, поэтому изучается первым. Суть его заключается в том, что необходимо будет «перебирать» все элементы массива на совпадение с заданными критериями или ключами. Самый простой не означает самый быстрый. Этот вид поиска очень затратный по времени, поэтому не рекомендуется к применению в массивах с большим количеством данных.
Пример функции линейного поиска:
int linSearch(int arr[], int requiredKey, int arrSize)
<
for (int i = 0; i < arrSize; i++)
<
if (arr[i] == requiredKey)
return i;
>
return -1;
>
Данный вид поиска подходит для поиска одиночного элемента в небольших несортированных массивах. Если массив большой, тогда лучше отсортировать его и применить один из методов, описанных ниже .
Двоичный или бинарный поиск элемента в массиве на С
-
Допустим , у вас есть отсортированный массив с простыми числами от 1 до 10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
-
Вам необходимо найти индекс значения числа «2». «2» будет ключ о м поиска , п оэтому на первом этапе массив поделится «пополам». Так как индексирование элементов в массиве начинается с 0, у нас получается , что 0 + 9 / 2 = 4 (0 , 5 отбрасывается , и индекс округляется). По д индексом 4 у нас стоит число 5 , это число сравнивается с нашим ключом. 5 не равно 2 и больше н его. Если бы «среднее» значение массива совпало с ключом, тогда массив бы прекратил работу.
-
Так как 5 больше 2, поиск значения продолжится в части массива, содержащей числа от 1 до 5, а числа от 6 до 10 «отбрасываются в сторону». Вторым шагом алгоритма будет поиск среднего значения в «укороченном» массиве: 0 + 4 / 2 = 2. Под индексом 2 у нас расположено число 3. 3 сравнивается с ключом. Алгоритм определит, что 3 не равно 2 и больше н его. Значит , будет третий шаг.
-
На третьем шаге еще часть массива после числа 3 «отбрасывается». Алгоритм ищет среднее значение в оставшихся индексах: 0 + 2 / 2 = 1. Под индексом 1 у нас располагается число 2 , это число сравнивается с нашим ключом. Алгоритм определяет, что число 2 равно нашему ключу 2, выдает нам соответствующий индекс числа и за канчивает свою работу.
Интерполирующий поиск элемента в массиве С
Интерполирующий поиск пришел из математики , и он не настолько сложен, как произносится. Его смысл сводится к тому, что необходимо определять область поиска заданного значения, вычисляя подобие расстояний между искомым элементом и всей областью. Как это выглядит в коде:
#include <iostream>
using namespace std;
int main ()
<
//Определяем массив со значениями, среди которых будет проходить поиск
int OwnArray [] <2, 3, 5, 7, 8, 90, 124, 232, 1001, 1236 >;
int y = 0; //определяем текущую позицию массива
int c = 0; //определяем левую границу массива, откуда будет начинаться поиск
int d = 9; //определяем правую границу массива, докуда будет продолжаться поиск
int WeSearch = 124; //определяем элемент, который ищем
bool found;
//Запускаем интерполяционный поиск в массиве С
for (found = false; (OwnArray[c] < WeSearch) && (OwnArray[d] > WeSearch) && | found;)
y = c + ((WeSearch — OwnArray[c]) * (d — c)) / (OwnArray[d] — OwnArray[c]);
if (OwnArray[y] < WeSearch)
c = y +1;
else if (OwnArray[y] > WeSearch)
d = y -1;
else
found = true;
>
//интерполяционный поиск в массиве окончен, тогда можно вывести результаты
if (OwnArray[c] == We Search)
cout < < WeSearch < < “Элемент найден“ < < c < < endl;
else if (OwnArray[d] == WeSearch)
cout < < WeSearch < < “Элемент найден“ < < d < < endl;
else
cout < < “Извините, элемент не найден“ < < endl;
return 0;
>
Простыми словами: этот метод вычисляет область, где может быть расположен искомый элемент ; если в этой области нет элемента, тогда границы области в массиве сдвигаются в ту или иную сторону. Этот метод чем-то похож на бинарный алгоритм, потому что в нем также «куски» массива постепенно отсеиваются, пока искомая область не будет сужена до 1 элемента. Если и в этом случае искомый элемент не будет найден, тогда его нет в массиве.
Заключение
-
«Решето Эратосфена»;
-
поиск с «барьером»;
-
и другие алгоритмы.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.