Бинарный поиск - раздел Образование, СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ Другим Относительно Простым Методом Доступа К Элементу Явля-
Ется Ме...
Другим относительно простым методом доступа к элементу явля-
ется метод бинарного (дихотомического, двоичного) поиска, который
выполняется в заведомо упорядоченной последовательности элемен-
тов. Записи в таблицу заносятся в лексикографическом (символьные
ключи) или численно (числовые ключи) возрастающем порядке. Для
достижения упорядоченности может быть использован какой-либо из
методов сортировки (см. 3.8).
В рассматриваемом методе поиск отдельной записи с определен-
ным значением ключа напоминает поиск фамилии в телефонном спра-
вочнике. Сначала приближенно определяется запись в середине таб-
лицы и анализируется значение ее ключа. Если оно слишком велико,
то анализируется значение ключа, соответствующего записи в сере-
дине первой половины таблицы, и указанная процедура повторяется в
этой половине до тех пор, пока не будет найдена требуемая запись.
Если значение ключа слишком мало, испытывается ключ, соответству-
ющий записи в середине второй половины таблицы, и процедура пов-
торяется в этой половине. Этот процесс продолжается до тех пор,
пока не будет найден требуемый ключ или не станет пустым интер-
вал, в котором осуществляется поиск.
Для того, чтобы найти нужную запись в таблице, в худшем слу-
чае требуется log2(N) сравнений. Это значительно лучше, чем при
последовательном поиске.
Программная иллюстрация бинарного поиска в упорядоченном
массиве приведена в следующем примере, где a - исходный массив,
key - ключ, который ищется; функция возвращает индекс найденного
элемента или EMPTY - если элементт отсутствует в массиве.
{===== Программный пример 3.5 =====}
Function BinSearch(a : SEQ; key : integer) : integer;
Var b, e, i : integer;
begin
b:=1; e:=N; { начальные значения границ }
while b<=e do { цикл, пока интервал поиска не сузится до 0 }
begin i:=(b+e) div 2; { середина интервала }
if a[i]=key then
begin BinSearch:=i; Exit; {ключ найден - возврат индекса }
end else
if a[i]<key then b:=i+1 { поиск в правом подинтервале }
else e:=i-1; { поиск в левом подинтервале }
end; BinSearch:=EMPTY; { ключ не найден }
end;
Трассировка бинарного поиска ключа 275 в исходной последова-
тельности:
75, 151, 203, 275, 318, 489, 524, 519, 647, 777
представлена в таблице 3.4.
Таблица 3.4
┌──────────┬───────┬───────┬───────┬─────────┐
│ Итерация │ b │ e │ i │ K[i] │
├──────────┼───────┼───────┼───────┼─────────┤
│ 1 │ 1 │ 10 │ 5 │ 318 │
│ 2 │ 1 │ 4 │ 2 │ 151 │
│ 3 │ 3 │ 4 │ 3 │ 203 │
│ 4 │ 4 │ 4 │ 4 │ 275 │
└──────────┴───────┴───────┴───────┴─────────┘
Алгоритм бинарного поиска можно представить и несколько ина-
че, используя рекурсивное описание. В этом случае граничные индек-
сы интервала b и e являются параметрами алгоритма.
Рекурсивная процедура бинарного поиска представлена в прог-
раммном примере 3.6. Для выполнения поиска необходимо при вызове
процедуры задать значения ее формальных параметров b и е - 1 и N
соответственно, где b, e - граничные индексы области поиска.
{===== Программный пример 3.6 =====}
Function BinSearch( a: SEQ; key, b, e : integer) : integer;
Var i : integer;
begin
if b>e then BinSearch:=EMPTY { проверка ширины интервала }
else begin
i:=(b+e) div 2; { середина интервала }
if a[i]=key then BinSearch:=i {ключ найден, возврат индекса}
else if a[i]<key then { поиск в правом подинтервале }
BinSearch:=BinSearch(a,key,i+1,e)
else { поиск в левом подинтервале }
BinSearch:=BinSearch(a,key,b,i-1);
end; end;
Известно несколько модификаций алгоритма бинарного поиска,
выполняемых на деревьях, которые будут рассмотрены в главе 5.
Все темы данного раздела:
СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Статические структуры относятся к разряду непримитивных
структур, которые, фактически, представляют собой структурирован-
ное множество примитивных, базовых, структур. Например, в
Векторы
ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одномерный массив) - структура
данных с фиксированным числом элементов одного и того же типа ти-
па. Каждый элемент вектора имеет уникальный в рамках
Логическая структура
Массив - такая структура данных, которая характеризуется:
- фиксированным набором элементов одного и того же типа;
- каждый элемент имеет уникальный набор значений индексов;
Физическая структура
Физическая структура - это размещение элементов массива в
памяти ЭВМ. Для случая двумерного массива, состоящего из
(k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс-
Адресация элементов с помощью векторов Айлиффа
Из выше приведенных формул видно, что вычисление адреса эле-
мента многомерного массива может потребовать много времени, пос-
кольку при этом должны выполняться операции сложения
Специальные массивы
На практике встречаются массивы, которые в силу определенных
причин могут записываться в память не полностью, а частично. Это
особенно актуально для массивов настолько больших раз
МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ
ЭЛЕМЕНТОВ. К данному типу массивов относятся массивы, у которых
местоположения элементов со значениями отличными от фонового, мо-
гут быть математически описаны,
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО
РАЗМЕЩЕНИЯ. Один из основных способов хранения подобных разрежен-
ных матриц заключается в запоминании ненулевых элементов в одно-
мерном массиве и идентификации
ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.
Методы последовательного размещения для представления разреженных
матриц обычно позволяют быстрее выполнять операции над матрицами
и более эффективно использовать память, чем мето
Множества
ЛОГИЧЕСКАЯ СТРУКТУРА. Множество - такая структура, которая
представляет собой набор неповторяющихся данных одного и того же
типа. Множество может принимать все зн
Числовые множества
Стандартный числовой тип, который может быть базовым для
формирования множества - тип byte.
Множество хранится в памяти как показано в таблице 3.3.
Таблица 3.3
&
Множество из элементов перечислимого типа
Множество, базовым типом которого есть перечислимый тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Множество от интервального типа
Множество, базовым типом которого есть интервальный тип,
хранится также, как множество, базовым типом которого является
тип byte. Однако, в памяти занимает место, которое зависит
Логическое и машинное представление записей
Запись - конечное упорядоченное множество полей, характери-
зующихся различным типом данных. Записи являются чрезвычайно
удобным средством для представления программных моделей ре
Таблицы
Когда речь шла о записях, было отмечено, что полями записи
могут быть интегрированные структуры данных - векторы, массивы,
другие записи. Аналогично и элементами векторов и массив
Структурами. Поиск
В этом и следующих разделах представлен ряд алгоритмов поис-
ка данных и сортировок, выполняемых на статических структурах
данных, так как это характерные операции логического уро
Последовательный или линейный поиск
Простейшим методом поиска элемента, находящегося в неупоря-
доченном наборе данных, по значению его ключа является последова-
тельный просмотр каждого элемента набора, который про
Структурами. Сортировка
Для самого общего случая сформулируем задачу сортировки та-
ким образом: имеется некоторое неупорядоченное входное множество
ключей и должны получить выходное множество тех же клю
Сортировки выборкой
СОРТИРОВКА ПРОСТОЙ ВЫБОРКОЙ. Данный метод реализует практи-
чески "дословно" сформулированную выше стратегию выборки. Порядок
алгоритма простой выборки
Еще одна модификация пузырьковой сортировки носит название
шейкер-сортировки. Суть ее состоит в том, что направления прос-
мотров чередуются: за просмотром от начала к концу следует прос-
мотр от конца к началу входного м
Сортировки включением
СОРТИРОВКА ПРОСТЫМИ ВСТАВКАМИ. Этот метод - "дословная" реа-
лизации стратегии включения. Порядок алгоритма сортировки просты-
ми вставками - O(N^2), ес
Сортировки распределением.
ПОРАЗРЯДНАЯ ЦИФРОВАЯ СОРТИРОВКА.Алгоритм требует представ-
ления ключей сортируемой последовательности в виде чисел в неко-
торой системе счисления P. Число прохо
Таблицы прямого доступа
Простейшей организацией таблицы, обеспечивающей идеально
быстрый поиск, вляется таблица прямого доступа. В такой таблице
ключ является адресом записи в таблице или может быть прео
Таблицы со справочниками
Одним из способов устранения этого недостатка является метод
справочников. Основная таблица содержит записи в произвольном по-
рядке. В дополнение к основной строится справочная и
Хешированные таблицы и функции хеширования
Как отмечалось выше, в каждой реальной таблице фактическое
множество ключей является лишь небольшим подмножеством множества
всех теоретически возможных ключей. Поскольку память яв
Новости и инфо для студентов