Последовательный массив. Поиск в последовательном массиве.
Поиск – процедура выделения из некоторого множества записей определенного подмножества, записи которого удовлетворяют некоторому заранее поставленному условию. Условие поиска часто называют запросом на поиск. Простейшее условие поиска – поиск по совпадению, т.е. равенство значения ключевого атрибута i-й записи р(i) и некоторого заранее заданного значения q. алгоритмы всех разновидностей поиска можно получить из алгоритмов поиска по совпадению.
Базовым методом доступа к массиву является ступенчатый поиск – предполагает упорядоченность обрабатываемых записей, причем безразлично по возрастанию и по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию. Простейшим вариантом ступенчатого поиска является последовательный поиск. Искомое значение q сравнивается с ключом первой записи, если значения не совпадают – с ключом второй записи и т.д. до тех пор, пока q не станет больше ключа очередной записи. Поиск с одинаковой вероятностью 1/М может окончиться на любой записи, поэтому С=(1/М)Σi=(M+1)/2 или С пропорционально М.
Рассмотрим двухступенчатый поиск в массиве, состоящем из записей. Для заданного М выбирается константа dl, называемая шагом поиска. Если необходимо отыскать запись со значением ключевого атрибута = q, производятся следующие действия. Значение qпоследовательно связывается с рядом величин р(1), р(1+dl), р(1+2dl),…, р(1+kdl) до тех пор, пока впервые будет достигнуто неравенство.
P (1+m*dl)>=q – здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер 1+m*dl и больше до тех пор, пока в процессе сравнений будет достигнут ключ >, больше, чем q. извлеченные при этом записи с ключом q образуют результат поиска. Эффективность поиска измеряется количеством произведенных сравнений.
Для двухступенчатого поиска среднее число сравнений примерно составляет С=М/(2*dl)+dl/2
Параметр dl – выбираемый, и естественно выбрать его так, чтобы минимизировалось С. dl – непрерывная переменная – производная = С’=-М/(2 dl^2)+(1/2)
Из условия С’=0 получаем dl= корень из М.
Вторая производная С’ ‘ в точке х = dl положительна, =>достигнуто минимальное значение С.
При n-ступенчатом поиске заранее выбираются константы n и S.
На 1 этапе ключевые атрибуты для сравнения с искомым ключом q выбираются из массива по закону арифметической прогрессии, начиная с р(1) и шагом dl=М/S (окружение в меньшую сторону). Когда впервые будет достигнут ключ р(k)>q, выбирается шаг d2=dl/S и организуется сравнение с этим шагом, начиная с р(k-dl). Описанные действия повторяются n раз, причем шаг на последней ступени поиска dn=1. Минимальное число сравнений достигается при S=M^(1/n). И кроме того существует оптимальное n=ln M.
Ступенчатый поиск имеет важный частный вариант – бинарный поиск, когда S=2. Для бинарного поиска вводится левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т.е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(А+В)/2 с окружением в меньшую сторону. Ключ i-й записи р(i) сравнивается с искомым значением q.
Если р(i)=q, то поиск заканчивается. В случае р(i)>q записи с номерами i+1, i+2,…M заведомо не содержат ключа q, и надо сократить интервал поиска, приняв В=i.
Аналогично при p(i)