Поиск элемента в массиве
💻 Информатика · 9 класс
Линейный и двоичный поиск, поиск максимума и минимума, подсчёт количества элементов с заданным свойством.
Поиск в массиве
Часто нужно узнать, есть ли в массиве нужное значение, и где именно оно находится. Эту задачу решают алгоритмы поиска. Поиск — одна из базовых операций обработки данных: прежде чем что-то изменить или посчитать, элемент обычно надо сначала найти. Рассмотрим два главных способа поиска и связанные с ними задачи.
Линейный поиск
Самый простой способ: перебираем элементы массива по очереди от начала и сравниваем каждый с искомым значением. Этот метод подходит для любого массива, в том числе для неупорядоченного.
nayden := -1
для i от 1 до n:
если a[i] = x то nayden := i
вывод nayden
Если значение не найдено, переменная остаётся равной -1 — это условный признак отсутствия. Линейный поиск прост, но при большом массиве может потребовать много сравнений.
Двоичный поиск
Двоичный (бинарный) поиск работает только в отсортированном массиве, зато выполняется очень быстро. На каждом шаге проверяют средний элемент и отбрасывают ту половину массива, где искомого значения точно нет. Так область поиска уменьшается вдвое за каждый шаг.
| Признак | Линейный поиск | Двоичный поиск |
|---|---|---|
| Нужна сортировка | нет | да |
| Скорость | медленнее | намного быстрее |
| Принцип | перебор подряд | деление пополам |
Поиск максимума
Чтобы найти наибольший элемент, берут первый элемент за «текущий максимум» и сравнивают его с остальными по очереди. Если встречается элемент больше, он становится новым максимумом:
max := a[1]
для i от 2 до n:
если a[i] > max то max := a[i]
Точно так же находят минимум, заменив знак сравнения. А с помощью отдельного счётчика можно подсчитать количество элементов с заданным свойством — например, сколько в массиве положительных чисел или чисел, кратных трём.
Поиск номера, а не значения
Часто важно знать не только наибольшее значение, но и его позицию в массиве. Для этого вместе с текущим максимумом запоминают и его индекс: при каждой замене максимума обновляют и номер. Такой приём нужен, например, чтобы потом обратиться к соседним элементам или переставить найденный элемент. Можно сочетать поиск и подсчёт: за один проход по массиву одновременно найти максимум, минимум и количество элементов с нужным свойством — это экономит время, потому что массив перебирается всего один раз, а не трижды.
Частые ошибки. Начинают поиск максимума с нуля, а не с первого элемента (ошибка при отрицательных числах); применяют двоичный поиск к неотсортированному массиву; останавливают линейный поиск на первом совпадении, когда требуется найти все вхождения.
Кратко о главном
- Линейный поиск перебирает все элементы и работает в любом массиве.
- Двоичный поиск делит массив пополам, но требует сортировки.
- Максимум и минимум ищут сравнением с текущим значением.
- Счётчик помогает подсчитать элементы с нужным свойством.
- Признак «не найдено» удобно хранить как значение -1.