§ 2. Поиск в массиве

Определения и обозначения

Массив — упорядоченная последовательность элементов одного типа, доступ к которым задаётся индексом. Например, массив целых чисел хранит несколько чисел, расположенных в определённом порядке. Такая структура позволяет хранить набор данных и обращаться к его частям по отдельности.

Элемент массива — значение, хранящееся в одной ячейке массива. Чтобы прочитать или изменить это значение, обращаются к ячейке по её индексу. Различение элементов помогает понять, что именно программа проверяет при поиске.

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

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

Как это устроено

Поиск начинают с уточнения задачи: важно решить, какое значение ищут и какой результат нужен. Иногда достаточно ответа «есть» или «нет», а иногда требуется индекс элемента либо количество его появлений. От этого зависит, когда можно остановить просмотр и что нужно сохранять во время работы алгоритма.

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

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

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

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

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

Сначала определите, какой результат требует задача: факт наличия, первое положение или количество появлений. Затем выберите строку таблицы и следуйте её правилу остановки. Особенно внимательно проверьте, не требует ли условие продолжить просмотр после первого совпадения.

Разбор задач

Проверка наличия числа

Условие. В массиве [4, 9, 2, 7] нужно проверить, есть ли число 2. Поскольку нужен только факт наличия, достаточно найти первое совпадение. Для примера считаем, что индексация начинается с нуля.

1. Сравниваем первый элемент 4 с числом 2: они не равны.
2. Проверяем следующий элемент 9: совпадения тоже нет.
3. Сравниваем третий элемент 2 с искомым числом и получаем совпадение.
4. Останавливаем просмотр: ответ уже известен, остальные элементы проверять не требуется.

Ответ: число 2 в массиве есть. Такой ход подходит для проверки наличия, потому что дальнейшие сравнения не изменят ответ «есть».

Поиск индекса первого совпадения

Условие. В массиве [6, 3, 8, 3, 5] требуется найти индекс первого элемента, равного 3. Примем нумерацию с нуля, как принято во многих языках программирования. Здесь недостаточно назвать само число: нужно определить его положение.

1. Начинаем с индекса 0: значение равно 6, поэтому переходим дальше.
2. На индексе 1 находится 3, значит, это первое совпадение; сохраняем индекс 1.
3. Завершаем просмотр, так как ищется именно первое вхождение.

Ответ: индекс первого элемента со значением 3 равен 1. Позднее в массиве есть ещё одна тройка, но она не меняет положение первого совпадения.

Подсчёт всех совпадений

Условие. В массиве [2, 5, 2, 7, 2, 9] нужно определить, сколько раз встречается число 2. Здесь требуется не первое положение, а общее количество. Поэтому нельзя останавливаться, когда найдена первая двойка.

1. Перед просмотром устанавливаем счётчик совпадений равным 0.
2. Проверяем элементы по очереди: при значении 2 увеличиваем счётчик на 1, а при другом значении оставляем его без изменения.
3. Двойки встречаются на индексах 0, 2 и 4, поэтому после каждой из них счётчик увеличивается.
4. Проверяем и оставшиеся элементы, чтобы убедиться, что новых совпадений нет.

Ответ: число 2 встречается 3 раза. Проверка всего массива гарантирует, что счётчик учитывает каждое вхождение.

Типичные ошибки

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

Индекс и значение элемента — не одно и то же: индекс показывает место, а значение хранится в этом месте. Путаница возникает, когда числа в массиве принимают за номера ячеек. Проверьте результат на небольшом массиве: например, в [6, 3, 8] значение 3 находится на индексе 1 при нумерации с нуля.

Если значение не найдено, нельзя использовать индекс, который должен был сохраниться при совпадении. Такая ошибка появляется, когда программа не предусматривает отдельный случай отсутствия значения. До обращения по найденному индексу проверьте, что совпадение действительно было, или выведите сообщение «не найдено».

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

Связь с другими темами

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

Поиск применяют при обработке списков: например, чтобы проверить наличие записи или найти подходящее значение. Он также связан с сортировкой и алгоритмами работы с коллекциями, потому что порядок данных влияет на выбор способа обработки. Умение точно сформулировать результат поиска помогает строить более сложные программы.

Что запомнить

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