6. Поиск

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

var a: array [0..N–1] of Item

Обычно тип Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному «аргументу поиска» x. Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как здесь рассматривается, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ.

С точки зрения теории множеств поиск можно рассматривать, как отображение множества X = {x1, x2, ..., xN} на множество X' = {xk}, X' является подмножеством X, и xk = xi. Если искомых данных в множестве X нет, то множество X' является пустым.


Поиск требуемой информации применяется ко всем основным структурам данных с произвольным доступом: массивам, спискам (одно- и двусвязным), деревьям, графам, таблицам.


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

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

Последовательный (или линейный) поиск – наиболее просто реализуемый метод поиска.

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


Примеры последовательного поиска с циклами for и while.


Программа линейного поиска на языке "Паскаль"

var
    nums: array [0..N] of real;

function search_s1(item: ^real; n: integer; key: real):integer;
var
    i: integer;
begin
    for i := 0 to N do
      if key = item[i] then
      begin
        search_s1 := i;
        break
      end
      else
        search_s1 := -1
end;

function search_s2(item: ^real; n: integer; key: real):integer;
var
    i: integer;
begin
    i:=0;
    search_s2 := -1;
    while (key <> item[i]) or ( i < n) do
    begin
      if key = item[i] then
        search_s2 := i;
      i := i + 1
    end
end;

Аналогичные процедуры на языке Си++:
int search_s1(float* item, int n, float key)
{
   for (int i = 0; i < N; i++)
     if (key == item[i])
       return i;
   return -1;
}

int search_s2(float* item, int n, float key)
{
   int i=0;
   while (key != item[i] || i < n)
   {
     if (key == item[i])
       return i;
     i++;
   }
   return -1;
}

Последовательный поиск в среднем случае выполнит проверку N/2 элементов, в лучшем – 1 элемента, а в худшем – N элементов.

Недостаток этого поиска – медленное выполнение при большом объеме просматриваемого массива.

Но если данные не отсортированы, то должен использоваться только последовательный поиск.

6.2 Двоичный поиск

Двоичный (или бинарный) поиск основан на итерационном сравнении ключа поиска со средним элементом массива.


При каждой итерации интервал анализа делится пополам (на 2): 1/2, 1/4, 1/8 и т.д., откуда этот метод поиска и получил свое название (ещё один вариант названия – дихотомический). В зависимости от результата сравнения, выбирается нижний или верхний интервал. Процесс продолжается до тех пор, пока не будет найдено совпадение или длина интервала анализа не станет равной единице, и если при этом нет совпадения, то фиксируется неудача поиска.


Этот метод поиска значительно эффективнее чем последовательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы).


В худшем случае выполняется не более

log2(N) + E

сравнений (где E < 0.0861), в связи с чем двоичный поиск ещё называется "логарифмическим поиском".


Программа двоичного поиска на языке "Паскаль"


function search_b(item: ^real; n: integer; key: real):integer;
var
    low, high, mid: integer;
begin
    search_b := -1;
    low := 0;
    high := n-1;
    while low <= high do
    begin
      mid := (low + high) / 2;
      if key < item[mid] then
        hig := mid - 1
      else
        if key > item[mid] then
          low := mid + 1
        else
          search_b := mid
    end
end;

Аналогичная процедура на языке Си++:
int search_b(float* item, int n, float key)
{
   int low, high, mid;
   low = 0;
   high= n - 1;
   while (low <= high)
   {
     mid = (low + high) / 2;
     if (key < item[mid])
       high = mid - 1;
     else
       if (key > item[mid])
         low = mid + 1;
       else
         return mid;
   }
   return -1;
}

Существуют модификации алгоритма:

Поиск с использованием чисел Фибоначчи

F(n) = F(n−1) + F(n−2), F(0) = 0, F(1) = 1, F(2) = 1, ...

F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Числа Фибоначчи используются вместо степеней двойки при делении интервала. В данном случае вместо деления используются только сложение и вычитание. Для этого требуется таблица чисел Фибоначчи, или процедура их вычисления, исходя из длины интервала. Данный метод проще реализуется при размере массива, на 1 меньше очередного числа Фибоначчи N + 1 = Fk.

6.3 Специальные виды поиска

Интерполяционный поиск произошел от естественного поиска данных в упорядоченном массиве человеком. Если известно, что искомый ключ k находится между некоторым "нижним" ключом kl и некоторым "верхним" ключом kh,

kl < k < kh

то следующее сравнение делается на расстоянии

(l − h)(k − kl) / (kh − kl)

от текущей позиции ki. Предполагается что данные в массиве возрастают в арифметической прогрессии.

Именно по такому алгоритму выполняется поиск нужной карточки в "бумажном" библиотечном каталоге, или страницы в книге.

Этот алгоритм эффективнее бинарного поиска только в случае арифметической прогрессии, так как на каждом шаге уменьшает интервал анализа не до n/2 а до sqr(ni) и требует в среднем около log2(log2(N)) шагов, если упорядоченные данные имеют равномерное распределение.


Недостаток этого алгоритма – затраты времени на дополнительные операции при внутреннем поиске. Разность между log2(log2(N)) и log2(N) становится весьма существенной при больших N, а типичные наборы данных (которыми для этого поиска часто являются файлы) недостаточно случайны.

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


Для поиска подстроки в строке могут использоваться алгоритмы Бойера–Мура (и его несколько модификаций) и Кнута–Морриса–Пратта.


Контрольные вопросы


1. Что такое поиск?
2. Что называется ключом поиска?
3. Какие известны методы поиска?
4. Какой из основных алгоритмов поиска является наиболее эффективным?
5. Какое требование предъявляется к структуре данных, в которой выполняется двоичный поиск?
6. Чем отличается поиск в массиве от поиска в списке?
7. Чем отличаются процедуры поиска в односвязном и двусвязном списках?
8. В чем заключается метод линейного поиска?
9. В чем заключается метод двоичного поиска?
10. Почему двоичный поиск получил такое название?
11. Какие известны варианты двоичного поиска?
12. Пригоден ли двоичный метод для поиска данных в неупорядоченной структуре?
13. Какой из методов поиска данных в массиве является более универсальным?
14. Существуют ли какие-нибудь недостатки у линейного поиска? Если да, то какие?
15. Перечислите особенности последовательного поиска.
16. В каких случаях применяется последовательный поиск?
17. Перечислите достоинства и недостатки последовательного поиска.
18. Соблюдение какого условия необходимо для применения к структуре данных оичного поиска?
19. Какими достоинствами обладает двоичный поиск?


Тест для самопроверки

< Назад | Вперед >

Хостинг от uCoz