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

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

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

Остальые известные человечеству (а может даже и не все %) методы поиска работают с упорядоченными данными. Во всех таких методах используется всякая возможность хотябы приблизительно вычислить координаты местоположения элемента в массиве данных.

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

Следующий элемент основан также на делении отрезка, но уже по другому принципу. Если я скажу название этого метода - фиббоначиев Вы наверняка догадаетесь с чем он связан. Хотя лучше объяснить %) Работа этого метода основана на числах фиббоначи. Эти числа вычисляются по формуле I_n=I_n-1+I_n-2. Нулевой и первый элемент этой последовательности равны единице, поэтому получается последовательность чисел фиббоначи: 1 1 2 3 5 8 13 21 34 ... Так вот при поиске методом фиббоначи ключевой элемент сравнивается со значениями граничных элементов отрезка образуемого числами фиббоначи I_n и I_n+1, при этом достаточно быстро вы можете найти отрезок содержащий нужный элемент. После нахождения этого отрезка на нем производится последовательный поиск.

Вы наверняка возмутились "почему в поиске фиббоначи используется последовательный поиск ?". И правильно возмутились, представляете какие гигантские отрезки будут получаться при больших членах последовательности. Поэтому видимо лучше скрестить поиск фиббоначи с бинарным поиском. Мне кажется скорость в этом случае должна несколько возрасти. Но погодите, сейчас рассказ о еще более быстром методе :)

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

               | (j-i)*(K-Ki) |
    d=цел.часть| ------------ |
               |   Kj - Ki    |

Тут d - это расстояние первоначального сравнения. Параметры i и j - номера соответственно первого и последнего элемента отрезка. Ki и Kj - это значения элементов в i и j позициях. Если все элементы исходного массива являются(или достаточно близки к ним) членами арифметической прогрессии, то поиск может пройти за одно сравнение. Если Вы не нашли нужный ключ с первого раза, то исходный отрезок поиска сужается и делается следующее сравнение с ключом расположенным на новом расстоянии d.