Массивы

Массивы

Предположим, что у нас имеется отсортированный массив. Как было показано ранее, алгоритм последовательного поиска даже при использовании выхода из цикла в случае отсутствия в списке искомого элемента принадлежит к классу O(n). Каким образом можно улучшить быстродействие?

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

Бинарный поиск работает следующим образом. Берем средний элемент массива. Равен ли он искомому элементу? Если да, то поиск успешно завершен. В противном случае, если искомый элемент меньше среднего, то можно сказать, что, если элемент присутствует в массиве, он находится в первой половине. С другой стороны, если искомый элемент больше среднего, он должен находиться во второй половине. Таким образом, одним сравнением мы разбили нашу проблему на две части. Теперь мы применяем тот же алгоритм к выбранной части массива: находим средний элемент и определяем, в какой половине (точнее уже в четвертой части) находится искомый элемент. Мы снова делим проблему на две части. Описанные операции продолжаются до тех пор, пока искомый элемент не будет найден (разумеется, если он присутствует в массиве).

Это и есть алгоритм бинарного поиска. Поскольку размер массива при каждом выполнении цикла уменьшается в два раза, быстродействие алгоритма будет выражаться как O(log(n)), т.е. скорость работы алгоритма примерно пропорциональна функции двоичного логарифма log(_2_) от количества элементов в массиве (таким образом, возведение количества элементов массива во вторую степень приведет к увеличению времени поиска только в два раза).

Ниже приведен пример выполнения бинарного поиска в массиве TList (функцию можно найти в файле TDTList.pas на Web-сайте издательства, в разделе сопровождающих материалов).

Листинг 4.9. Бинарный поиск в отсортированном массиве TList

function TDTListSortedIndexOf(aList : TList; aItem : pointer;

aCompare : TtdCompareFunc) : integer;

var

L, R, M : integer;

CompareResult : integer;

begin

{задать значения для индексов первого и последнего элементов}

L := 0;

R := pred(aList.Count);

while (L <= R) do begin

{вычислить индекс среднего элемента}

M := (L + R) div 2;

{сравнить значение среднего элемента с искомым значением}

CompareResult := aCompare(aList.List^[M], aItem);

{если значение среднего элемента меньше искомого значения, переместить левый индекс на позицию до среднего индекса}

if (CompareResult < 0) then

L := succ(M)

{если значение среднего элемента больше искомого значения, переместить правый индекс на позицию после среднего индекса}

else if (CompareResult > 0) then

R := pred(M)

{в противном случае искомый элемент найден}

else begin

Result := M;

Exit;

end;

end;

Result := -1;

end;

Для описания подмассива, рассматриваемого в текущий момент, используются две переменных - L и R, которые хранят, соответственно, левый и правый индексы. Первоначально значения этих переменных устанавливаются равными 0 (первый элемент массива) и Count-1 (последний элемент массива). Затем мы входим в цикл While, из которого выйдем после обнаружения в массиве искомого элемента или когда значение переменной L превысит значение переменной R, что означает, что искомый элемент в массиве отсутствует. При каждом выполнении цикла вычисляется индекс среднего элемента (фактически это среднее значение между L и R). Затем значение элемента со средним индексом сравнивается с искомым значением. Если значение среднего элемента меньше, чем искомое, мы переносим левый индекс на позицию после среднего. В противном случае мы переносим правый индекс на позицию перед средним. Таким образом, мы определяем новый подмассив для поиска. Если же значение среднего элемента равно искомому, поиск завершен.

Для примера на рис. 4.1 приведены шаги, выполняемые при бинарном поиске буквы d в отсортированном массиве, содержащем буквы от a до k. На шаге (а) переменная L указывает на первый элемент (индекс 0), а R - на последний (индекс 10). Это означает, что значение переменной M будет составлять 5. Далее мы выполняем сравнение: значение элемента с индексом 5 равно f, а это больше искомого значения d.

Рисунок 4.1. Бинарный поиск в массиве

Согласно алгоритму, мы устанавливаем значение R равным M-1 (таким образом, правая граница подмассива теперь находится слева от среднего элемента). Это означает, что значение R теперь равно 4. Новое значение среднего индекса будет равно 2, как показано на шаге (b). Выполняем сравнение: буква c (значение элемента с индексом 2) меньше, чем d.

Теперь, в соответствии с алгоритмом, необходимо установить индекс L за индексом M (т.е. M+1 или 3). Новое значение переменной M на шаге (с) равно 3. Выполняем сравнение: элемент с индексом 3 содержит букву d, а это и есть наше искомое значение. Поиск завершен.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Массивы

Из книги автора

Массивы Массив — это пронумерованный набор переменных (элементов), фактически хранящийся в одной переменной. Доступ к отдельному элементу массива выполняется по его порядковому номеру, называемому индексом. А общее число элементов массива называется его


8.3. Массивы

Из книги автора

8.3. Массивы Интерпретатор bash поддерживает одномерные массивы с неограниченным числом элементов. В других оболочках существуют определенные ограничения на массивы, например, в ksh максимальное число элементов массива ограничено 1024 элементами.Нумерация элементов


Массивы

Из книги автора

Массивы По умолчанию указатели, передаваемые через параметры, полагаются указателями на единичные экземпляры, а не на массивы. Для передачи массива в качестве параметра можно использовать синтаксис С для массивов и/или специальные атрибуты IDL для представления


Массивы

Из книги автора

Массивы Массивы в С++ объявляются с указанием количества элементов массива в квадратных скобках после имени переменной массива. Допускаются двумерные массивы, т.е. массив массивов. Ниже приводится определение одномерного массива, содержащего 10 элементов типа int:int


R.8.2.4 Массивы

Из книги автора

R.8.2.4 Массивы В описании T D, в котором D имеет видD1 [ выражение-константа opt ]описывается идентификатор типа "… массив T". Если выражение-константа присутствует (§R.5.19), то оно должно иметь целочисленный тип и значение, большее 0. Это выражение задает число элементов массива.


Массивы

Из книги автора

Массивы Для создания множества одинаковых объектов в 3ds Max есть специальная команда Array (Массив). Преимущество массивов заключается в том, что можно быстро создать большое количество объектов, сразу же указав, на сколько они будут сдвинуты, на какой угол повернуты и как


8.1. Массивы

Из книги автора

8.1. Массивы В Ruby массивы индексируются целыми числами; индексация начинается с нуля, как в языке С. На этом, впрочем, сходство и заканчивается.Массивы в Ruby динамические. Можно (хотя это и не обязательно) задать размер массива при создании. Но после создания он может расти без


Массивы

Из книги автора

Массивы Массив — это упорядоченная именованная совокупность однотипных значений, к которым можно обращаться по их порядковому номеру (индексу). Для описания массивов в языке Object Pascal используют следующие формы:• array [1..N1] of type — одномерный массив фиксированного размера


МАССИВЫ 

Из книги автора

МАССИВЫ      Вы уже знаете, что массив представляет собой группу элементов одного типа. Когда нам требуется для работы массив, мы сообщаем об этом компилятору при помощи операторов описания. Для создания массива компилятору необходимо знать тип данных и требуемый класс


Массивы

Из книги автора

Массивы Во многих отношениях массивы являются простейшей структурой данных. Проще могут быть только такие базовые типы данных, как integer или Boolean. Массив (array) представляет собой последовательный список определенного количества элементов. Все элементы в массиве


Массивы

Из книги автора

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


Массивы

Из книги автора

Массивы Предположим, что у нас имеется отсортированный массив. Как было показано ранее, алгоритм последовательного поиска даже при использовании выхода из цикла в случае отсутствия в списке искомого элемента принадлежит к классу O(n). Каким образом можно улучшить


Массивы

Из книги автора

Массивы Динамические массивы Очень простой пример…Const MaxBooleans = (High(Cardinal) – $F) div sizeof(boolean);Type TBoolArray = array[1..MaxBooleans] of boolean; PBoolArray = ^TBoolArray;Var B: PBoolArray; N: integer;BEGIN N:= 63579; {= получение памяти под динамический массив.. =} GetMem(B, N*sizeof(boolean)); {= работа с массивом… =} B^[3477]:= FALSE; {= возвращение


Массивы

Из книги автора

Массивы Массив представляет собой набор элементов одного типа, каждый из которых имеет свой номер, называемый индексом (индексов может быть несколько, тогда массив называется многомерным).Массивы в PascalABC.NET делятся на статические и динамические.При выходе за границы


Массивы

Из книги автора

Массивы Мы уже довольно много знаем о переменных и работе с ними. Но наши знания все еще неполны. Так, мы ничего пока не знаем о массивах — особом способе хранения данных, доступном в ActionScript. Давайте же выясним, что это