Поиск элемента в упорядоченном массиве.

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

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

1.Определить середину массива.

2.Если элемент, находящийся в середине массива, совпадает с искомым, то поиск завершен.

3.Если элемент, находящийся в середине массива, больше искомого, применить бинарный поиск к первой половине массива.

4.Если элемент, находящийся в середине массива, меньше искомого, бинарный поиск необходимо применить ко второй половине массива.

5. Пункт 1-4 повторять, пока размер области поиска не уменьшается до нуля. Если это произойдет – ключа в массиве нет.

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

Рассмотренный алгоритм бинарного поиска представлен блок-схемой на рис.7.2.

 

 

Нетрудно заметить, что в худшем случае (искомого элемента в массиве нет) алгоритм бинарного поиска сделает не более O(log₂N) шагов. Это объясняется тем, что на каждом шаге поиска вдвое уменьшается область поиска. До того, как она станет равной одному элементу, произойдет не более O(log₂N) таких уменьшений.

Фонетический поиск

Под фонетическим поиском понимается поиск по нечеткому значению ключа, если в качестве ключа используется фамилия, так как она воспринимается на слух. Наибольшее распространение при организации фонетического поиска получил метод "Soundex" [4]. Метод создает для фамилии ключ, причём похожим фамилиям или неверным написаньям одной фамилии будет соответствовать один ключ. Поэтому, если оператор городской справки, кассир в банке, авиадиспетчер или кто-либо другой наберёт вашу фамилию неверно, доступ к вашей записи в базе данных все равно будет получен, так как поиск ведётся по ключам.

Первоначально метод "Soundex" развит Маргарет К. Оуделли и Робертом К. Расселом [см.U.S.Patents 1261167 (1918), 1435663 (1922)]. Метод "Soundex" заключеется в следующем:

1.Оставить первую букву фамилии; все буквы а,е,h,i,о,u,w,у, стоящие на других местах, вычеркнуть.

2.Оставшимся буквам (кроме первой) присвоить следующие значения:

b, f, p, v= 1;

l= 4;

c, g, j, k, q, s, x, z= 2;

m, n=5;

d, t=3;

r= 0.

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

4.Дописывая в случае надобности нули или опуская лишние цифры, преобразовать полученное выражение в форму "буква, цифра, цифра, цифра".

Например, фамилии Euler, Gauss, Hilbert, Knuth, Lloyd и Lukasiewicz имеют коды соответственно Е460, G200, H416, K530, L300, L222.

Разумеется, такая система собирает вместе не только родственные, но и достаточно различные фамилии. Приведенные выше шесть кодов могли быть получены из фамилий Ellery, Ghosh, Heilbronn, Kant, Ladd и Lissajous. С другой стороны, такие родственные имена, как Rogers и Rodgers, Sinclair и St.Clair или Tchebysheff и Chebyshev, имеют разную кодировку. Но, вообще говоря, система "Soundex" намного увеличивает вероятность обнаружить имя под одной из его масок [4-6].

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

Алгоритмы сортировки

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

Большая часть данного раздела посвящена рассмотрению алгоритмов внутренней сортировки. В качестве объекта сортировки рассматривается массивов, т.е. сортируемые данные размещаются в оперативной памяти, организованной линейно. В разделе рассматриваются следующие алгоритмы внутренней сортировки:

· сортировка методом пузырька;

· сортировка вставки;

· сортировка выбором;

· пирамидальная сортировка;

· быстрая сортировка.

Методы внутренней сортировки хорошо иллюстрируют как одну и ту же задачу можно решить с помощью различных алгоритмов с различной степенью эффективности.

Из методов внешней сортировки в данном разделе рассмотрен только метод сортировки слиянием, позволяющий объединить несколько отсортированных файлов в один.

Временная сложность алгоритмов приводится без доказательства.