ПОИСКОМ называется процедура выделения из некоторого множества записей определенного подмножества, записи которого удовлетворяют некоторому заранее поставленному условию. Условие поиска часто называют запросом на поиск.
Простейшим условием поиска является ПОИСК ПО СОВПАДЕНИЮ, т. е. равенство значения ключевого атрибута i-й записи р(0 и некоторого заранее заданного значения q. Алгоритмы всех разновидностей поиска можно получить из алгоритмов поиска по совпадению.
Базовым методом доступа к массиву является СТУПЕНЧАТЫЙ ПОИСК. Этот метод предполагает упорядоченность обрабатываемых записей, причем безразлично, по возрастанию или по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений ключевого атрибута p(i).
Простейшим вариантом ступенчатого поиска (его можно назвать одноступенчатым) является ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК.
Искомое значение q сравнивается с ключом первой записи, если значения не совпадают, с ключом второй записи и т. д. до тех пор, пока q не станет больше ключа очередной записи.
Поиск с одинаковой вероятностью r(i)=l/M может окончиться на любой записи, поэтому
С = (1/М)- Е i = (М + 1)/2 или С ~ М.
Рассмотрим двухступенчатый поиск в массиве, состоящем из М записей. Для заданного М выбирается константа dl, называемая ШАГОМ ПОИСКА. Если необходимо отыскать запись со значением ключевого атрибута, равным q, производятся следующие действия.
Значение q последовательно сравнивается с рядом величин
р(1), p(l+dl), p(l+2*dl),..., p(l+k*dl) до тех пор, пока будет впервые достигнуто неравенство p(l+m*dl)=>q. Здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер l+m*dl и больше, до тех пор, пока в процессе сравнений будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q ОБРАЗУЮТ РЕЗУЛЬТАТ ПОИСКА.
|
|
Эффективность поиска измеряется количеством произведенных сравнений. Для двухступенчатого поиска среднее число сравнений примерно составит:
C = M/(2*dl) + dl/2.
Параметр dl выбираемый и естественно выбрать его так, чтобы минимизировалось С. Будем считать dl непрерывной переменной и вычислим производную
C'=-M/(2*dlA2)+l/2.
Из условия С'= 0 получаем dl=SQR(M). Вторая производная С" в точке х = dl положительна, следовательно, достигнуто минимальное значение С.
При п-ступенчатом поиске заранее выбираются константы п и S. На первом этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону арифметической прогрессии, начиная с р(1) и шагом dl=M/S (округление в меньшую сторону). Когда будет впервые достигнут ключ p(k) > q, выбирается шаг d2 = dl/S и организуются сравнения с этим шагом, начиная с p(k-dl). Описанные действия повторяются п раз, -причем шаг на последней ступени поиска dn= 1.
Минимальное число сравнений достигается при S=MA(l/n), и, кроме того, существует оптимальное п=1п(М).
Ступенчатый поиск имеет важный частный вариант – БИНАРНЫЙ ПОИСК, когда S=2.
Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(A+B)/2 с округлением в меньшую сторону. Ключ i-й записи p(i) сравнивается с искомым значением q. Если p(i) =q, то поиск заканчивается. В случае p(i)>q записи с номерами i+1, i+2,..., М заведомо не содержат ключа q, и надо сократить интервал поиска, приняв B=i. Аналогично при p(i)<q надо взять A=i. Далее середина интервала вычисляется заново, и все действия повторяются. Если будет достигнут нулевой интервал, то требуемой записи в массиве нет Достаточно легко оценить максимальное число сравнений Cm при поиске данных бинарным методом. Сокращение интервала поиска на каждом шаге в худшем случае приведет к интервалу нулевой длины, что соответствует отсутствию в массиве искомого значения ключевого атрибута. После первого сравнения интервал поиска составит М/2 записей, после
|
|
второго - М/4 и т. д. Когда интервал поиска впервые станет меньше 1, применяемая схема округления результата деления даст нулевой интервал и поиск закончится. Это соответствует неравенству М/(2АСга)<=1 (знак Л обозначает возведение в степень), откуда Cm~log M. Среднее число сравнений при бинарном поиске составляет C=log(M) -1. Для обоснования представим все возможные разветвления алгоритма бинарного поиска в виде дерева. Число уровней дерева соответствует Ст. Половина возможных сравнений расположена на последнем уровне и половина— на первых (log(M)-l) уровнях. Определение лучшего метода поиска (из рассмотренных выше последовательного, двухступенчатого и бинарного) опирается на следующие рассуждения. Во всех трех случаях время поиска является функцией от числа записей М. Конкретные выражения составляют:
• для последовательного поиска Т1~МилиТ1=к1*М;
• для двухступенчатого поиска T2~SQR(M) или T2=k2(SQR(M));
• для бинарного поиска ТЗ-logM или T3=k3*logM.