Меню
Главная

Статистика

 

 


Настало время обратиться к механизму ускоренного поиска элемента вектора по значению, - ускоренного в сравнении с последовательным просмотром. Он известен под именами метод дихотомии или метод половинного деления. Как обычно, за скорость взимается плата: массив должен быть упорядочен по ключам. Сам по себе этап предварительного упорядочения, или сортировки, обходится недешево, во всяком случае - дороже однократного линейного поиска. Более подробное его обсуждение нам еще предстоит.

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

Итак, вот постановка задачи:

Алгоритм E3-1

В упорядоченном по ключам векторе Mas длиной N>1 найти элемент, имеющий заданное значение sample, и вернуть его индекс, либо установить факт отсутствия таких элементов. Кроме того, будем считать, не умаляя при этом общности, что элементы массива отсортированы по неубыванию.

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

  • Определяем середину интервала поиска.

  • Сравниваем образец с элементом, расположенным посередине. Если образец оказался больше, то областью дальнейшего поиска становится правая половина; в противном случае - левая половина интервала, но в любом случае индексный интервал уменьшается вдвое. (Если осуществить еще одну проверку, то можно установить и совпадение, после чего дальнейшие шаги не обязательны.)

  • Если остался интервал единичной длины, то переходим к заключительному шагу 4, в противном случае - к шагу 1.

  • Либо единственный элемент интервала совпадает с образцом, либо - искомого элемента в массиве нет.


Пример #1.

Задумайте число от 1 до 100. Ваше число больше 50? -- Да. -- Ага, остался интервал от 51 до 100. Ваше число больше 75? -- Нет. -- Теперь остается промежуток от 51 до 75. И так далее.

Напишем соответствующую паскаль-функцию. 

const N=100;
type
  index1 = 0..N-1;
  massive1 = array [index1] of byte;

procedure InitArray1 (var Mas: massive1);
var i: index1;
begin
  for i:= 0 to N-1 do
    Mas[i]:= N-i;
end;
                
type
  index1 = 0..N-1; {N > 1}
  Programmer = record of
    Name: string; Number: byte; Time: word
  end;
var Results = array [index1] of Programmer;
        
type
  index1 = 0..N-1; {N > 1}
  massive1 = array [index1] of item;

function Search2 (Mas: massive1;
  left, right: index; sample: item): boolean;
var l, r, middle: index1;
begin
  l := left; r:= right;
  while l<r do begin
    middle:= (l+r) div 2;
    if Mas[middle] < sample then l:= middle + 1
    else r := middle
  end;
  if M[l] = sample then Search2:= true
  else Search2:= false
end;
            
type
  index1 = 0..N-1; {N>1}
  massive1 = array [index1] of item;

procedure SelectionSort (var Mas: massive1);
var i: index1;
begin
  for i := (N-1) downto 1 do
    Swap(Mas[i], Mas[IndexMax(Mas,0,i)]);
end;

Несколько замечаний стоит добавить. Механизм поиска гарантирует обнаружение компоненты с заданным значением, если таковая присутствует в массиве. Если перевести переменную l в ранг параметра или сделать ее глобальной, то удастся вернуть также индекс компоненты. Однако, если таких элементов несколько, - естественно, они располагаются друг за другом, - то уже нельзя ничего сказать относительно расположения найденного внутри группы собратьев. Стоит еще обратить внимание, что предлагаемый вариант функции, как и ранее рассмотренный E2-1, работает для подмассива. Что касается быстродействия, то в "большом" массиве дихотомия заметно опережает последовательный поиск. Поскольку на каждом шаге алгоритма интервал поиска уменьшается вдвое, то количество шагов не превосходит élog2Nù, соответственно, асимптотическая эффективность метода половинного деления оценивается как O(log2N).

Назад