§ 12. Поиск элементов с заданными свойствами

12.1. Линейный поиск

Рассмотрим, как осуществляется поиск данных, хранящихся в массиве.

Среди разновидностей простейших задач поиска, встречающихся на практике, можно выделить следующие типы:

1. Найти хотя бы один элемент, равный заданному элементу x. В результате получают i — индекс (номер) элемента массива, такой что a[i] = x. 
2. Найти все элементы, равные заданному x. В результате получают количество таких элементов и (или) их индексы.

Иногда поиск организуется не по совпадению с элементом x, а по выполнению некоторых условий. Примером может служить поиск элементов, удовлетворяющих условию: x1 ≤ a[i] ≤ x2, где x1 и x2 заданы.

Если нет никакой дополнительной  информации о разыскиваемых данных, то самый простой подход — последовательный просмотр элементов массива.

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

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

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

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

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