Виды поиска и их методы:

- Линейный поиск Слово последовательный содержит в для себя главную идею способа. Начиная с первого, все элементы массива поочередно просматриваются и сравниваются с искомым. Если на каком-то шаге текущий элемент окажется одинаковым разыскиваемому, тогда элемент считается отысканным, и в качестве результата ворачивается номер этого элемента, либо иная информация о нем.
- Двоичный поиск (Бинарный поиск) Метод использует стратегию дели и владычествуй, а конкретно: заданная последовательность делится на две одинаковые доли и поиск осуществляется в одной из этих долей, которая потом также делится надвое, и так до тех пор, пока обнаружится наличие искомого элемента или его отсутствие. Использовать эту операцию, уменьшая каждый раз зону поиска в два раза, позволительно только исходя из того факта, что элементы последовательности заранее упорядочены.
- Интерполяционный поиск. В базе интерполяционного поиска лежит операция интерполирование. Интерполирование нахождение промежных значений величины по имеющемуся дискретному комплекту известных значений. Интерполяционный поиск работает только с упорядоченными массивами; он похож на бинарный, в том смысле, что на каждом шаге вычисляется некая область поиска, которая, по мере исполнения алгоритма, сужается. Но в отличие от двоичного, интерполяционный поиск не разделяет последовательность на две одинаковые доли, а вычисляет примерное размещение ключа (искомого элемента), ориентируясь на расстояние между искомым и текущим значением элемента.