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

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

Алгоритм поиска можно представить таким образом:

1. Сравнить первый элемент с требуемым.

2. Если элементы совпадают, то поиск закончен, элемент найден.

3. Если элементы не совпадают, то сравнивается следующий элемент, при этом вновь начинается процесс (2).

4. Этот процесс продолжается до тех пор, пока не будет достигнут конец массива или пока не будет найден требуемый элемент.

Этот алгоритм целесообразно применять для любой неупорядоченой последовательности чисел, или неотсортированного массива.

Поиск делением пополам

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

Основная идея состоит в том, что выбранный случайным образом элемент массива, при сравнении с требуемым, если он не равен ему, даст две ветви поиска

- при условии, что выбранный элемент массива больше искомого, из рассмотрения исключаются все элементы большие, чем выбранный;

- при условии, что выбранный элемент массива меньше искомого, из рассмотрения исключаются все элементы меньшие, чем выбранный;

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