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

Последовательный метод поиска называют также методом последо­вательного перебора. Это самый универсальный, наиболее простой и самый длительный метод поиска. Последовательный поиск можно использовать при любом способе организации информационного масси­ва, для любых структур данных, при любой форме аргумента поиска. В процессе поиска осуществляется последовательное обращение к каж­дой записи массива и при этом определяется, удовлетворяет ли данная запись критерию выдачи.

Последовательный поиск в массиве из 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. На этот раз искомый элемент найден. В двоичном поиске количество сравнений в худшем случае равно log₂ n.

БЛОЧНЫЙ ПОИСК

Упорядоченные по возрастанию ключей записи таблицы группируются в блоки, каждый из которых содержит равное количество записей (оптимальное их число равно квадратному корню из числа записей в файле). Па каждом шаге считывается первая запись каждого блока и ее ключ сравнивается с аргументом поиска. Шаги повторяются, начиная с первой записи таблицы, до тех пор, пока не будет выполнено одно из трех условий:
1) ключ записи совпадает с аргументом поиска - и этом случае поиск завершается успешно;
2) обнаружена запись с ключом, превышающим apгумент поиска - в том случае начинается последовательный просмотр записей предыдущего блока и сравнение их ключей с аргументом поиска до тех пор, пока либо не будет обнаружена искомая запись (успешный поиск), либо блок не будет просмотрен полностью (поиск неудачен):
3) достигнут конец файла - в этом случае поиск завершается неудачно.

Не нашли, что искали? Воспользуйтесь поиском: