скачать doc
4. Поиск в массиве 48
4.1. Линейный поиск 48
4.2. Разработка алгоритма бинарного поиска 50
4.3. Анализ алгоритма бинарного поиска 52
4.4. Оптимизация программы бинарного поиска 56
5. ПОИСК В МАССИВЕ
5.1. Линейный поиск
Рассмотрим задачу поиска элемента в одномерном массиве.
Дано: 1) число элементов массива;
2) массив типа array [index] of Elem;
3) : Elem элемент для поиска;
4) искомый элемент в массиве есть, т. е. .
Условие 4 можно записать в виде утверждения (: : ) или в форме с квантором счета
(: ) > 0.
Требуется: найти первое вхождение в массив , т. е. найти , такое, что () & ( : : ).
Далее будем записывать утверждение ( : : ) более кратко, а именно . Тогда постутверждение для этой задачи можно записать в виде
Post: () & () & ().
Инвариант может быть получен устранением конъюнктивного члена () из постусловия Post, т. е. Inv: () & (). Если в качестве условия выхода из цикла взять устраненный конъюнктивный член (), то получим как раз требуемое: Inv & (условие выхода) Post.
Это приводит к программе вида
или к варианту с циклом while-do
Пусть теперь условие 4 постановки задачи не выполняется, т. е. заранее неизвестно, есть ли элемент в массиве .
Требуется: если , то установить = true и кроме того указать , такое, что () & () & (); если (), то установить = false.
Требуемое постусловие можно записать в виде
(), (5.1)
где введено обозначение
= (() & () & ()).
Очевидно, для решения задачи необходимо просматривать все элементы массива, пока не будет найден элемент, равный . Фактически индуктивная функция над последовательностью со стационарным значением = true. Рассматривая «чтение» последовательности в естественном порядке, получим алгоритм
Инвариантом цикла здесь является утверждение () & (). Учитывая условие выхода из цикла, получаем при его завершении постутверждение (() or ) & () & () & (), где учтено, что при тело цикла выполняется хотя бы один раз. Из этого утверждения следует требуемое постусловие (5.1).
В задаче поиска с заранее неизвестным исходом удобно использовать следующий прием: добавим к массиву дополнительный элемент, играющий роль «барьера», тогда задача поиска сведется к первоначальной постановке (известно, что) и может быть решена программой
Оценивая эффективность линейного поиска по числу требуемых сравнений (или ), легко заметить, что в лучшем случае (при ) поиск завершится за один шаг, в худшем за шагов (в варианте без барьера), а в среднем за шагов (в предположении, что все различны и вероятность события равна ).
5.2. Разработка алгоритма бинарного поиска
Существенно лучший алгоритм, чем последовательный поиск, можно предложить в случае, когда массив упорядочен.
Дано: 1) : Integer;
2) array of Ordinal; Pred: (: : )}
3) : Ordinal.
Требуется: либо найти индекс , определяющий место в массиве, такой, что при , либо указать, что x a[1] или a[n] < x.
Удобно добавить «идеальные» элементы и , которые можно использовать для записи утверждений, но которые не должны входить в исполняемые инструкции программы. Тогда требуемое постутверждение примет вид Post: () & (). Если такой индекс найден, то саму задачу поиска можно решить дополнительной проверкой:
что выражается постутверждением .
В качестве основной идеи алгоритма возьмем следующую: пусть сначала о локализации значения среди значений ничего неизвестно, т. е. предутверждение можно дополнить утверждением ; далее при работе алгоритма будем рассматривать интервал локализации , где ; причем на каждом шаге этот интервал должен уменьшаться, т. е. величина должна убывать. Эта идея реализуется инвариантом цикла () & () , ограничивающей функцией и условием завершения цикла . Отметим, что формально инвариант можно получить из постутверждения () заменой границ интервала и на и соответственно. Из предусловия будет следовать инвариант, если цикл инициализировать следующим способом: . Таким образом, имеем набросок программы, изображенной на рис. 5.1. Тело цикла должно обеспечивать уменьшение интервала при сохранении инварианта. Очевидно, уменьшить интервал можно, выбрав значение индекса внутри интервала и сравнив с . При этом следует брать таким, что и еще не сравнивались, т. е. . Пусть , тогда необходимо изменить левую границу, причем так, чтобы удовлетворить инвариант, т. е. , и,
| |
| Рис. 5.1. Набросок алгоритма |
следовательно, . Из аналогичных соображений при должно получаться . Таким образом, тело цикла примет вид
При этом действительно, при условии , верном до выполнения тела цикла, получим после завершения тела цикла.
Выбирая различными способами значение , получим различные алгоритмы поиска. Например, при имеем аналог линейного поиска. Здесь в случае поиск заканчивается, а при размер интервала уменьшается всего на 1. Ясно, что более эффективный алгоритм можно получить, выбирая значение на каждом шаге так, чтобы длина интервала уменьшалась быстрее. Идея деления интервала пополам приводит к следующему алгоритму двоичного поиска:
Отметим, что выбор значения удовлетворяет условию .
Эффективность алгоритма двоичного (бинарного) поиска обсуждается далее.
Задания.
1) Покажите, что в качестве ограничивающей функции в случае бинарного поиска можно взять функцию .
2) Определите смысл результата работы этого алгоритма в случае предусловия (: : ).
3) Приведите алгоритм бинарного поиска, обеспечивающий постусловие Post: .
4) Приведите алгоритм бинарного поиска, обеспечивающий постусловие Post: .
5.3. Анализ алгоритма бинарного поиска
При разработке алгоритма бинарного поиска использовались лишь сравнения вида , где , . Определим наихудшее с точки зрения быстродействия число сравнений, требуемое алгоритмом.
Теорема 1. Максимальное число сравнений, требуемое алгоритмом бинарного поиска для нахождения места предъявленного значения среди , есть
.
Для доказательства теоремы рассмотрим так называемое дерево бинарного поиска. Каждому сравнению в алгоритме сопоставим узел дерева и обозначим его так, как показано на рис. 5.2, а. В узле дерева (в круге) записано вычисляемое на данном шаге значение , а сверху слева и справа от него значения границ рассматриваемой части массива и соответственно. К ветвям и подвешиваются аналогичные узлы: справа для случая и слева для случая . При узел не содержит продолжений (является листом дерева) и обозначается (рис.5.2, б) специальным образом (номером, заключенным в квадрат). Самый верхний (первый) узел называется корнем дерева. Построенное таким образом дерево описывает все возможные исходы сравнений применительно к заданным и . На рис. 5.3 изображено дерево бинарного поиска для ().
Рис. 5.3. Дерево бинарного поиска для ()
Отметим, что в таком дереве все внутренние узлы имеют двух сыновей, поскольку на любом шаге цикла левая и правая части массива не пусты. Исходам поиска соответствуют листья дерева, пронумерованные от 1 до . Внутренние узлы содержат номера элементов массива, с которыми может сравниваться значение , т. е. все номера от 1 до . Для данных и последовательность сравнений, требуемых алгоритмом бинарного поиска, задает путь в дереве от корня к результирующему листу.
Определим уровень узла в дереве следующим образом: уровень корня равен нулю, уровень любого другого узла на единицу больше уровня его непосредственного предка (отца). Глубину дерева определим как значение максимального из уровней его листьев.
При получится ровное дерево с листьями только на последнем -м уровне. Например, для дерево имеет вид, изображенный на рис. 5.4, а. Очевидно, максимальное число сравнений алгоритма бинарного поиска для заданного определяется глубиной дерева бинарного поиска. Пусть , или в иной форме записи
.
Покажем, что глубина дерева бинарного поиска в массиве из элементов. Доказательство проведем индукцией по . При = 1 имеем (), дерево изображено на рис. 5.4, б и его глубина равна 1.
Пусть для некоторого имеем и глубина дерева есть (индуктивное предположение). Покажем, что при глубина дерева равна + 1. Пусть чётно. На первом шаге алгоритма бинарного поиска перейдем к одной из двух задач: в левом поддереве с количеством исходов /2 либо в правом поддереве с количеством исходов /2. Поскольку из неравенства при чётном следует неравенство , то с учетом индуктивного предположения получим глубину дерева + 1. При нечётном на первом шаге задача разделится на две подзадачи: в левом поддереве с числом исходов , в правом . Поскольку из неравенства при нечётном следует и далее , то с учётом индуктивного предположения глубина дерева равна + 1. Теорема доказана.
Как видно, число сравнений в алгоритме равно либо (лист на последнем уровне), либо 1 (лист на предпоследнем уровне). Число листьев на этих уровнях легко определить следующим образом. Пусть или , где . Пусть и число листьев на уровнях и 1 соответственно. Тогда += общее число листьев. С другой стороны, число внутренних узлов на предпоследнем уровне равно и к каждому из них подвешены по два узла последнего уровня (листа), т. е. . Таким образом, имеем два уравнения для определения и :
+=,
,
из которых следует и .
Отсюда легко подсчитать среднее число сравнений, требуемое алгоритмом бинарного поиска, при условии, что все исходы (варианты попадания в различные интервалы) равновероятны. Действительно,
.
Очевидно, что , причем при (), т. е. в случае ровного дерева.
Насколько хорош алгоритм бинарного поиска? Можно ли предложить лучший по числу сравнений алгоритм? На эти вопросы отвечает следующая теорема.
Теорема 2. Для произвольного алгоритма поиска в массиве, использующего сравнения, можно подобрать такие исходные данные и , что применение к ним этого алгоритма потребует не менее сравнений.
Для доказательства теоремы рассмотрим последовательности вопросов, на каждый из которых дается ответ: да или нет. Каждой такой последовательности можно сопоставить последовательность из нулей и единиц. Если применение алгоритма к исходным данным и потребовало ровно сравнений, а его применение к данным и дало тот же результат (ту же «01»-последовательность) за первые шагов, то дальнейших сравнений уже не потребуется и итог будет таким же, как и в первом случае, поскольку порожденная алгоритмом последовательность сравнений рассматриваемого вида определит один и тот же интервал локализации элементов и (с точки зрения сравнения с элементами массива предъявляемые и «выглядят» одинаково). Следовательно, среди получающихся «01»-последовательностей: а) ни одна не является началом другой и б) нет совпадающих последовательностей, соответствующих разным интервалам локализации. Если ограничиться длиной последовательности , то всего таких последовательностей будет . Ясно также, что их должно быть не меньше, чем число исходов применения алгоритма (число распознаваемых ситуаций), т. е. и, следовательно, или, так как m целое число, то .
Теорема доказана.
Сопоставление теорем 1 и 2 показывает, что алгоритм бинарного поиска является оптимальным (наилучшим по числу сравнений).
Задание. Пусть известно, что . Требуется найти номер , такой, что . Приведите алгоритм решения этой задачи, требующий сравнений. Докажите его оптимальность.
5.4. Оптимизация программы бинарного поиска
При рассмотрении вопроса об оптимальности алгоритма бинарного поиска учитывалось только число требуемых сравнений. Не учитывались другие операции, а также «накладные расходы» программы (на организацию цикла, работу с индексами и т. п.). Оказывается, программу можно значительно улучшить, модифицировав ее и уменьшив «накладные расходы».
Для определенности положим, что глобальные константы и типы задаются, например, описанием
const nMax = 2048; nMax1= 2049;
type index=1..nMax; index0=0..nMax; index1=1..nMax1;
DimVec=index;
ElemT= Integer;
Vec = array [index] of ElemT;
Начнем с полученного ранее алгоритма, оформленного в виде процедуры BinSearch1:
procedure BinSearch1(n: DimVec; var a: Vec; x: ElemT; var q:Boolean;
var L: index1);
{ арг : n, a, x; рез : q, L }
{ Pred: (ALL i: 1<=i<n: a[i]<a[i+1]) }
{ Post: (1<=L<=n+1) & (a[L1]<x<=a[L]) & }
{ (q = (1<=L<=n)&(a[L]=x)) }
var R: index1; m: index;
begin
L := 1; R := n + 1; { a[L1]<x<=a[R] }
while L <> R do
begin { (1<=L<R<=n+1) & (a[L1]<x<=a[R]) }
m := (L + R) div 2;
if a[m] < x then L := m + 1 else R := m
{ (1<=L<=R<=n+1) & (a[L1]<x<=a[R]) }
end { while };
{ (1<=L<=n+1) & (a[L1]<x<=a[L]) }
if L <> n + 1 then q := (x = a[L]) else q := False
end { BinSearch1 }
Рассмотрим далее другой вариант бинарного поиска в виде процедуры:
procedure BinSearch2 (n: DimVec; var a: Vec; x: ElemT; var q: Boolean; var L: index0);
{ арг : n, a, x; рез : q, L }
{ Pred: (ALL i: 1<=i<n : a[i]<a[i+1]) }
{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }
{ (q = (0<=L<=n1)&(a[L+1]=x) ) }
var R: index1; m: index;
begin
L := 0; R := n + 1; { a[L]<x<=a[R] }
while L + 1 <> R do
begin { (0<=L<R1<=n) & (a[L]<x<=a[R]) }
m := (L + R) div 2;
if a[m] < x then L := m else R := m
end { while };
{ (0<=L<=n) & (a[L]<x<=a[L+1]) }
if L <> n then q := (x = a[L + 1]) else q := False
end { BinSearch2 }
Отличие этого варианта лишь в том, что интервал локализации нумеруется по своей левой границе: & .
Следующее преобразование проведем в предположении, что длина массива, в котором осуществляется поиск, заранее известна. Пусть, например, . Из анализа алгоритма бинарного поиска (см. 5.3) известно, что число итераций в цикле while-do равно либо , либо 1, где =. При (для некоторого ) дерево бинарного поиска является ровным и число итераций в цикле while-do всегда равно . Этот факт можно использовать для оптимизации цикла. Перед циклом преобразуем исходный интервал к интервалу длины , где (при имеем ):
i := 512; if a[i] < x then L := n – i + 1 else L := 0;
здесь интервал локализации задается левой границей и длиной :
(a[L] < x <= a[L + i]) & (i = 512 = 2j) & (j = 9).
В самом цикле также вместо пары переменных L и R будем использовать пару переменных L и . В результате получим алгоритм
procedure BinSearch3 ({n: DimVec;} var a: Vec; x: ElemT;
var q: Boolean; var L: index0);
{ арг : a, x; рез : q, L }
{ Pred: (n=1000) & (ALL i : 1<=i<n : a[i]<a[i+1]) }
{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }
{ (q = (0<=L<=n1)&(a[L+1]=x) ) }
const n = 1000; { ! }
var i: 1..512; m: index;
begin
i := 512; if a[i] < x then L := n – i + 1 else L := 0;
{ (a[L]<x<=a[L+i]) & (i=512=2^j) & (j=9) & (L0=L) }
while i <> 1 do
begin
i := i div 2; m := L + i;
if a[m] < x then L := m else { };
{ (i=2^j) & (0<=j<9) & (a[L]<x<=a[L+i]) & (L0<=L<=L0+511) }
{ & (L+i<=n+1) }
end { while }; { Bound: j = log2(i) }
{ (0<=L<=n) & (a[L]<x<=a[L+1]) }
if L <> n then q := (x = a[L + 1]) else q := False
end{ BinSearch3 }
Важно, что теперь цикл выполняется при любом ровно 9 раз (), а сравнение производится при , где пробегает значения 256, 128, 64, 32, 16, 8, 4, 2, 1. Этот факт явным образом учитывается в окончательной версии алгоритма:
procedure BinSearch4 ({n: DimVec;} var a: Vec; x: ElemT;
var q: Boolean; var L: index0 );
{ арг : a, x; рез : q, L }
{ Pred: (n=1000) & (ALL i: 1<=i<n: a[i]<a[i+1]) }
{ Post: (0<=L<=n) & (a[L]<x<=a[L+1]) & }
{ (q = (0<=L<=n1)&(a[L+1]=x) ) }
const n = 1000; { ! }
begin L := 0;
if a[ 512 ] < x then L := n – 512 + 1; { a[L]<x<=a[L+512] }
if a[L + 256] < x then L := L + 256; { a[L]<x<=a[L+256] }
if a[L + 128] < x then L := L +128; { … }
if a[L + 64] < x then L := L + 64;
if a[L + 32] < x then L := L + 32;
if a[L + 16] < x then L := L + 16;
if a[L + 8] < x then L := L + 8;
if a[L + 4] < x then L := L + 4;
if a[L + 2] < x then L := L + 2; { … }
if a[L + 1] < x then L := L + 1; { (a[L]<x<=a[L+ 1]) & (0<=L<=n) }
if L <> n then q := (x = a[L + 1]) else q := False
end { BinSearch4 }
Здесь цикл явным образом развернут в последовательность операторов и исключена операция div 2. В [16] приводятся сравнительные данные выполнения оптимизированного (BinSearch4) и неоптимизированного (типа BinSearch1) вариантов алгоритмов бинарного поиска, реализованных на разных языках программирования и выполненных на различных вычислительных машинах. Оптимизированный вариант работает быстрее в 2…5 раз. В [16] окончательный вариант программы отмечен как вариант «не для слабонервных». Первое знакомство с ним (без учета его «происхождения»), как правило, озадачивает. Получение этого варианта алгоритма бинарного поиска из корректной процедуры BinSearch1 с учетом утверждений, присутствующих во всех промежуточных и конечном вариантах, доказывает корректность процедуры BinSearch4 и позволяет понять ее работу (а также оценить ее эстетическую привлекательность).