Алгоритм поиска в таблице

Данная глава посвящена решению простой поисковой задачи: находить данные, хранящиеся в памяти компьютера с определённой идентификацией. Например, в вычислительной задаче найти f(x) по значению x и таблице значений функции f; в лингвистической – найти английский эквивалент данного русского слова.

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

Существует две возможности окончания поиска: либо поиск оказался удачным, то есть позволил определить положение соответствующей записи, содержащей К; либо неудачным, то есть показал, что К не может быть найден ни в одной из записей. После неудачного поиска иногда желательно вставить в таблицу новую запись, содержащую К. Алгоритм, который делает это, называется поиском со вставкой.

1. Последовательный поиск

Последовательные поиск реализует следующую процедуру: начни с начала и продвигайся, пока не найдёшь нужный ключ; тогда остановись. Рассмотрим три алгоритма.

Алгоритм S (последовательный поиск).

Имеется таблица записей R1,R2,…,Rn (N≥1), снабжённых ключами K1,K2,…,Kn. Алгоритм предназначен для поиска записи с ключом К.

1. Установить начальное значение i=1;

2. Если Ki=K, то алгоритм завершён (идти на п. 5), запись Ri – искомая;

3. Перейти к следующей записи: i=i+1;

4. Если i≤N, то перейти на шаг 2, иначе – искомой записи в таблице нет;

5. Конец алгоритма.

Время работы алгоритма зависит от количества сравнений. Пусть обращение к записям происходит с равной вероятностью . Тогда среднее число сравнений

; СКО числа сравнений ≈0,289N.

Для ускорения работы алгоритма применяется алгоритм Q (быстрый последовательный поиск) – предполагается, что в конце стоит фиктивная запись RN+1.

2. Если Ki=K, то перейти к п.4, иначе

3. Перейти к следующей записи: i=i+1 и вернуться к п.2;

4. Если i≤N, то поиск прошёл удачно, в противном случае – неудачно (i=N+1);

Ускорение работы алгоритма до 30% по сравнению с алгоритмом S и достигается за счёт удаления одного сравнения из цикла.

Алгоритм Т(последовательный поиск в упорядоченной таблице).

Имеется таблица записей R1,R2,…,Rn,, причём ключи упорядочены по возрастанию: K1 >К. Это позволяет избежать зацикливания при K> KN.

Если значение К с равной вероятностью принимает все возможные значения, то в случае удачного поиска алгоритм Т не лучше алгоритма Q. Однако отсутствие нужной записи алгоритм Т позволяет обнаружить примерно в два раза быстрее.

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

До сих пор предполагалось, что с равной вероятностью может потребоваться поиск любого аргумента, однако часто такое предположение неправомерно.

Читайте также:  Как поставить windows вместо linux

Пусть ключ Ki будет разыскиваться с вероятностью pi, причём p1+p2+…+pN=1. Время удачного поиска при больших N пропорционально числу сравнений С, среднее значение которого будет минимальна при p1≥p2≥…≥pN, то есть когда наиболее часто используемые записи расположены в начале таблицы.

Рассмотрим распределение

2. Прямой поиск в упорядоченной таблице

Снимем ограничение иметь лишь последовательный доступ к таблице, при этом получим возможность эффективно использовать отношение порядка в упорядоченной таблице.

Бинарный поиск (дихотомический, логарифмический).

Суть его: сначала сравнить К со средним ключом в таблице; по результату сравнения можно определить, в какой половине таблицы продолжить поиск, применяя при этом ту же процедуру. После не более чем log2N сравнений либо ключ будет найден, либо установлено его отсутствие.

Алгоритм В (бинарный поиск). Найти аргумент К в таблице записей R1,R2,…,Rn, ключи которых упорядочены по возрастанию: K1 К8 – ключ, соответствующий «середине» и первым (корневым) круглым узлом дерева будет 8.

Если К К8, то поиск идёт в правом поддереве.

Неудачный поиск ведёт в один из внешних квадратных узлов от 0 до N. Например, узел 6 будет достигнут тогда и только тогда, когда К6 k -1 ≤N≤2 k удачный поиск, использующий алгоритм В, требует минимум 1, максимум К сравнений. Неудачный поиск требует k сравнений при N=2 k -1 либо k-1 или k сравнений при 2 k -1 ≤ N k -1.

Следствие: алгоритм В требует максимум [log2N]+1 сравнений, среднее число сравнений при удачном поиске .

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

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9175 — | 7317 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Поиск в упорядоченной таблице

Алгоритм последовательного поиска

Последовательный поиск

Введение в поиск

Алгоритмы поиска занимают важное место в прикладных алгоритмах. Обычно данные хранятся в определенном образом упорядоченном наборе. Найти некоторую запись из этого набора — вот классическая задача программирования, вокруг которой сгенерировано множество идей [1, 3, 9, 10, 13].

Пусть мы имеем таблицу, состоящую из записей (табл. 3.1). Первое поле каждой записи содержит ключ (например, табельный номер); второе — фамилию и так далее. Ключом может любое поле записи.

Иванов
Андреев
Сидоров
Петров

Основная задача поиска — найти запись с заданным ключом.

Все алгоритмы поиска, в зависимости от того, упорядочена таблица или нет, разбиваются по две большие группы. Упорядоченность понимается как наличие хотя бы одного отсортированного поля — а именно, ключевого.

Наиболее примитивный, а значит, и наименее эффективный, способ поиска— это обычный последовательный просмотр записей таблицы [9,11]. Метод применяется к таблице, организованной как массив. Предложим, что к— массив из п ключей; г— массив записей такой, что k(i) — ключ для записи r(i); key — аргумент поиска. Запишем в переменную search наименьшее целое число /, такое, что k(i) = key, если такое / существует, и -1 в противном случае.

Читайте также:  E3272 прошивка под всех операторов
for ( search=-l, i=0; i

Алгоритм индексно-последовательного поиска прост. Предположим, что к — массив из п ключей; г — массив записей такой, что k(i) является ключом для записи r(i); key — аргумент поиска. Пусть — массив ключей в индексе; pindex — массив указателей в индексе на записи. Размер основной таблицып. Размер индексной таблицыindsize.

i = 0;
while ( ( i
k r i ключ запись I
8 ] — ^——- ч—— >
14 ] i ^——— т——— s
26 ,s ———— ^————
387 I ———————————— -> i
.409. ]|
LS12 L )]
540 1 I ч———— ч———— ч
567 ) ————- *———— 4
1 583 1 *—————— *—————- * i
5d2 1 ^———— ^———— ^
1——— 1——— h ‘ ■ ■ ■ i ч——— ^——- гУ i

Рис. З.1. Схема хранения информации при индексно-последовательном поиске

Достоинство алгоритма заключаются в том, что сокращаются время поиска, так как последовательный поиск первоначально ведется в индексной таблице, имеющей меньший размер, чем основная таблица; когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей основной таблицы.

Бинарный поиск.Аргумент сравнивается с ключом среднего элемента в массиве [9, 11]. Если они равны, то поиск успешен. В противном случае поиск осуществляется аналогично в левой и правой частях массива. Алгоритм определяется рекурсивно, однако на практике применяется нерекурсивная версия ввиду её большой эффективности.

Дата добавления: 2014-11-29 ; Просмотров: 1032 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

«Начни с начала и продвигайся, пока не найдёшь нужный ключ; тогда остановись». Такая последовательная процедура является очевидным способом поиска; удобно начать наши рассмотрения с неё, так как на ней основаны многие более сложные алгоритмы. Несмотря на свою простоту, последовательный поиск содержит ряд очень интересных идей.

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

Алгоритм S. (Последовательный поиск.) Имеется таблица записей R1,R2. Rn, снабженных соответственно ключами K1,K2. Kn. Алгоритм предназначен для поиска записи с данным ключом K. Предполагается, что N≥ 1.

S1. Установить i ≤1.

S2. Если K=Ki, алгоритм оканчивается удачно.

S3. Если K<>Ki, увеличить i на 1.

T1. Установить i Ki [R1,R2. Ri исключаются из рассмотрения].

Читайте также:  Функция естьnull в запросе 1с

Умело действуя в каждом из этих случаев, можно сэкономить много времени по сравнению с последовательным поиском, если только не слишком близко к концам таблицы. Таким образом, упорядочение ведет к эффективным алгоритмам.

Бинарный поиск

Пожалуй, первым приходит в голову следующий очевидный метод: сначала сравнить K со средним ключом в таблице. Результат сравнения позволит определить, в какой половине файла продолжить поиск, применяя к нему ту же процедуру, и т.д. После не более чем примерно log2 N сравнений либо ключ будет найден, либо будет установлено его отсутствие. Такая процедура иногда называется «логарифмическим поиском» или «методом деления пополам», но наиболее употребительный термин — бинарный поиск.

Недостатком бинарного поиска является необходимость последовательного сохранения списка, что осложняет выполнение операции добавления и удаления элемента.

Основная идея бинарного поиска довольно проста, детали же нетривиальны, и для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей. Одна из наиболее популярных реализаций метода использует два указателя — l и u, соответствующие верхней и нижней границам поиска, и состоит в следующем.

Алгоритм B. ( Бинарный поиск). С помощью данного алгоритма разыскивается аргумент K в таблице значений R1,R2. Rn, ключи которых расположены в возрастающем порядке: K1 Ki, то перейти на B5; если K=Ki, алгоритм заканчивается удачно.

B4. [Корректировка u]. Установить u

Одна важная модификация. Соблазнительно вместо трёх указателей l, u, i использовать лишь два: текущее положение i и величину его изменения E; после каждого сравнения, не давшего равенство, мы могли бы установить i Ki, то перейти на U4; если K = Ki, алгоритм заканчивается удачно.

U3. [Уменьшение i]. (Мы определили положение интервала, где нужно продолжать поиск. Он содержит m или m-1 записей; i указывает на первый элемент справа от интервала.) Если m=0, то алгоритм оканчивается неудачно. В противном случае установить i Ki, то перейти на F4; если K=Ki, алгоритм заканчивается удачно.

3. [Уменьшение i ]. Если q=0, то алгоритм заканчивается неудачно. Если q<>0,то установить i 1,то установить i =K1, а когда K принадлежит B2, то K ,B2, в котором K1 находится ан j-ом месте. Если j=i, то необходимый элемент найден; если j>i, то i-ое наибольшее значение ищется с подсписке B1; если j 4

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.