ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ

ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ

ПОИСКОМименуется процедура выделения из некого огромного количества записей определенного подмножества, записи которого удовлетворяют некому заблаговременно поставленному условию. Условие поиска нередко именуют запросом на поиск.

Простым условием поиска является ПОИСК ПО СОВПАДЕНИЮ, т. е. равенство значения главного атрибута i-й записи р(0 и некого заблаговременно данного значения q. Методы всех разновидностей поиска можно ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ получить из алгоритмов поиска по совпадению.

Базисным способом доступа к массиву является СТУПЕНЧАТЫЙ ПОИСК. Этот способ подразумевает упорядоченность обрабатываемых записей, при этом индифферентно, по возрастанию либо по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений главного атрибута p(i).

Простым вариантом ступенчатого поиска (его можно именовать одноступенчатым) является ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ Поочередный ПОИСК.

Разыскиваемое значение q сравнивается с ключом первой записи, если значения не совпадают, с ключом 2-ой записи и т. д. до того времени, пока 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. Тут завершается 1-ая ступень поиска. На 2-ой ступени q поочередно сравнивается со всеми ключами, которые имеют номер l+m*dlи больше, до того времени, пока в процессе сравнений будет достигнут ключ, больший, чем ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ q. Извлеченные при всем этом записи с ключом q ОБРАЗУЮТ Итог ПОИСКА.

Эффективность поиска измеряется количеством сделанных сравнений. Для двухступенчатого поиска среднее число сравнений приблизительно составит:

C = M/(2*dl) + dl/2.

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

C'=-M ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ/(2*dlA2)+l/2.

Из условия С'= 0 получаем dl=SQR(M). 2-ая производная С" в точке х = 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)

второго - М/4 и т. д. Когда интервал поиска в первый раз станет меньше 1, используемая схема округления ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ результата деления даст нулевой интервал и поиск завершится. Это соответствует неравенству М/(2АСга)<=1(символ Л обозначает строительство в степень), откуда Cm~log M. Среднее число сравнений при бинарном поиске составляет C=log(M) -1. Для обоснования представим все вероятные разветвления метода бинарного поиска в виде дерева. Число уровней дерева ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ соответствует Ст. Половина вероятных сравнений размещена на последнем уровне и половина— на первых (log(M)-l) уровнях. Определение наилучшего способа поиска (из рассмотренных выше поочередного, двухступенчатого и бинарного) опирается на последующие рассуждения. Во всех 3-х случаях время поиска является функцией от числа записей М. Определенные выражения составляют:

• для поочередного поиска Т1~МилиТ ПОИСК В ПОСЛЕДОВАТЕЛЬНОМ МАССИВЕ1=к1*М;

• для двухступенчатого поиска T2~SQR(M) либо T2=k2(SQR(M));

• для бинарного поиска ТЗ-logM либо T3=k3*logM.


pokazanie-k-karotidnoj-endarterektomii-u-bolnogo-s-tranzitornimi-ishemicheskimi-atakami-1.html
pokazaniya-bolshinstvo-iz-izvestnih-v-nastoyashee-vremya-boleznej.html
pokazaniya-i-protivopokazaniya-dlya-primeneniya-banok-gorchichnikov-grelok-kompressov-tehnika-postanovki.html