ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСКПоследовательный метод поиска называют также методом последовательного перебора. Это самый универсальный, наиболее простой и самый длительный метод поиска. Последовательный поиск можно использовать при любом способе организации информационного массива, для любых структур данных, при любой форме аргумента поиска. В процессе поиска осуществляется последовательное обращение к каждой записи массива и при этом определяется, удовлетворяет ли данная запись критерию выдачи. Последовательный поиск в массиве из N записей требует в среднем (N + 1)/2 сравнений (единица в числителе появляется при нечетном N). В худшем случае, когда искомая запись окажется последней в массиве или ее не будет там вовсе, потребуется N сравнений. Последовательный поиск — единственно возможный в неупорядоченных неструктурированных массивах. Процедура последовательного поиска в неупорядоченном массиве может быть несколько ускорена. Любой алгоритм поиска содержит блок проверки на окончание массива. Проверка обычно осуществляется всякий раз перед обращением к очередной записи. Однако проверка на окончание массива может осуществляться не при каждом сравнении. Для этого в конец массива включается (N + 1)-я фиктивная запись с ключом, равным искомому. Тогда проверка на окончание массива осуществляется лишь при совпадении аргумента поиска со значением ключа текущей записи. Если эта запись находится внутри массива, то поиск заканчивается удачно и нужная запись считается найденной. Если же эта запись оказалась (N+ 1)-й, то поиск считается неудачным, т.е. нужной записи нет в массиве. (Во внутреннем цикле выполняется две проверки. Сначала проверяется, достиг ли индекс i конца массива, а затем выясняется, не равен ли элемент x[i] искомому. Первую проверку можно исключить, добавив элемент-метку в конце массива. Теперь внутренний цикл содержит только операцию увеличения индекса, обращение к элементу массива и проверку.) Последовательный поиск в неупорядоченном массиве потребует меньше времени, если для массива организован общий справочник. Так как объем справочника существенно меньше объема основного массива, то и поиск в нем будет происходить быстрее.
Двоичный поиск Если данные, в которых производится поиск, отсортированы, для нахождения элемента можно применять метод, намного превосходящий предыдущий — двоичный поиск [1]. В нем применяется метод половинного деления. Сначала проверим средний элемент. Если он больше, чем искомый ключ, проверим средний элемент первой половины, в противном случае — средний элемент второй половины. Будем повторять эту процедуру до тех пор, пока искомый элемент не будет найден либо пока не останется очередного элемента. Например, чтобы найти число 4 в массиве 1 2 3 4 5 6 7 8 9 при двоичном поиске сначала проверяется средний элемент — число 5. Поскольку оно больше, чем 4, поиск продолжается в первой половине: 1 2 3 4 5 Средний элемент теперь равен 3. Это меньше, чем 4, поэтому первая половина отбрасывается. Поиск продолжается в части 4 5. На этот раз искомый элемент найден. В двоичном поиске количество сравнений в худшем случае равно log2 n. БЛОЧНЫЙ ПОИСК Упорядоченные по возрастанию ключей записи таблицы группируются в блоки, каждый из которых содержит равное количество записей (оптимальное их число равно квадратному корню из числа записей в файле). Па каждом шаге считывается первая запись каждого блока и ее ключ сравнивается с аргументом поиска. Шаги повторяются, начиная с первой записи таблицы, до тех пор, пока не будет выполнено одно из трех условий:
Не нашли, что искали? Воспользуйтесь поиском:
|