Как найти номер вхождения элемента массива

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

Например,

Потренируйтесь в этой проблеме

Простым решением было бы запустить линейный поиск в массиве и вернуть первое или последнее вхождение данного элемента. Проблема с этим подходом заключается в том, что его временная сложность в наихудшем случае равна O(n), куда n это размер ввода. Это решение также не использует тот факт, что ввод отсортирован. Мы можем легко решить эту проблему в O(log(n)) время, изменив алгоритм бинарного поиска.

Поиск первого вхождения элемента

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

Ниже приведена программа на C, Java и Python, которая демонстрирует это:

Поиск последнего вхождения элемента

Чтобы найти последнее вхождение элемента, измените стандартный двоичный поиск, чтобы он продолжал поиск даже при обнаружении цели. Вместо этого обновите результат до mid и продолжим поиск вправо (в направлении более высоких индексов), т. е. модифицируем наше пространство поиска, изменив низкие значения на mid+1 при нахождении цели в середине индекса.

Ниже приведена реализация C, Java и Python, основанная на приведенной выше идее:

Временная сложность приведенных выше решений равна O(log(n)) и не требует дополнительного места.

 
Упражнение:

1. Напишите рекурсивную версию приведенных выше решений.

2. Проверьте, встречается ли данное целое число больше, чем n/2 раз в отсортированном массиве.

 
Использованная литература:

Для поиска индекса элемента в массиве можно использовать методы indexOf (для первого вхождения) и lastIndexOf (для последнего вхождения).

А как можно найти индекс в массиве объектов? Например индекс при первом вхождении нужного объекта?

Например есть массив объектов:

let inputArr = [{name:'bruce', age:40, city:'gotham'},
                {name:'barry', age:25, city:'fallville'},
                {name:'diana', age:30, city:'themyscira'}
               ];

Как получить индекс, где в свойстве name значение barry? Если писать так:

inputArr.indexOf('barry');

то выведет -1, а ожидаемое значение — 1. Может циклом перебирать все значения? Может есть простые способы?

_{orig post https://stackoverflow.com/q/8668174/6104996}

Для поиска по массиву в 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}

Заключение

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

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