           ЧАСТЬ 2. АЛГОРИТМЫ ПОИСКА

           Постановка задачи.  Имеется N элементов-записей в исходном файле,
        каждая из которых сопровождается ключом поиска K[1] ... K[N] и неко-
        торой информационной частью,  которую мы можем не рассматривать  без
        потери  общности.  Требуется найти позицию ключа,  имеющего заданное
        значение X. Запросы на поиск поступают последовательно и в некоторых
        случаях  известны  вероятности  поступления  каждого из них P[1] ...
        P[N].  В зависимости от количества элементов файла  N,  диапазона  и
        равномерности распределения значений ключей K[i],  вероятностей зап-
        росов на поиск конкретных значений Х наиболее подходящим может  ока-
        заться  один  из известных методов и структур данных,  которые будут
        описаны ниже.

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

           Название этой  группы методов произошло от использования последо-
        вательного списка в качестве структуры данных для  хранения  ключей.
        Список называют упорядоченным,  если он упорядочен по значениям клю-
        чей, в противном случае он не называется упорядоченным, хотя некото-
        рый  порядок  ему  можно  придать за счет размещения в начале списка
        элементов, которые ищутся наиболее часто, то есть в порядке убывания
        вероятностей запросов P[1] ... P[N].

           6.1. Последовательный поиск в неупорядоченном файле

           Алгоритм поиска имеет вид:

         for i=1 to N
        ┌────────────────────────────────────────────┐
        │if(X=K[i]) Конец: поиск удачен.             │
        └────────────────────────────────────────────┘
         Конец: поиск неудачен.

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*N
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.
           Среднее время удачного поиска можно значительно  сократить,  если
        вероятности  появления запросов на поиск различных ключей сильно от-
        личаются друг о другаи и ключи располагать в порядке убывания  веро-
        ятностей. Алгоритм в этом случае не изменяется, но должен быть пред-
        варительный этап упорядочения списка.  Также предполагается, что но-
        вые ключи при неудачном поиске не вставляются в список.

           6.2. Последовательный поиск по связанному списку.

           Вероятности появления  запросов  на поиск часто не известны зара-
        нее.  В этом случае можно использовать эмпирический алгоритм, дающий
        на  практике хорошие результаты:  каждый раз при удачном поиске най-
        денный ключ переставляется в начало списка. Естественно такие перес-
        тановки удобно делать на связанном списке.  Каждому ключу K[i] соот-
        ветствует поле связи L[i], указывающее на следующий логически за ним
        ключ. На первый элемент указывает поле связи L[0].
         ┌────┬────┐           ┌────┬────┐             ┌────┬────┐
         │K[1]│L[1]├──> ...  ─>┤K[i]│L[i]├─>─  ...  ──>┤K[N]│L[N]├─>  =0
         └─┬──┴────┘           └────┴────┘             └────┴────┘
          ┌┴───┐
          │L[0]│
          └────┘
           Алгоритм имеет следующий вид.

         m=0; lm=L[m];
         while (lm ╪ 0) do
        ┌────────────────────────────────────────────┐
        │           ┌──────────────────────────────┐ │
        │           │ Поиск удачен.Перестановка    │ │
        │if(X=K[lm])│ ключа K[lm] в начало списка  │ │
        │           ├──────────────────────────────┤ │
        │           │L[0]=lm;                      │ │
        │           │L[m]=L[lm];                   │ │
        │           │Конец алгоритма.              │ │
        │           └──────────────────────────────┘ │
        │ m=lm; lm=L[m];                             │
        └────────────────────────────────────────────┘
         Конец: поиск неудачен.

           Этот алгоритм легко модифицируется и для случая, когда после не-
        удачного поиска ключ Х должен быть вставлен первым в список.
           Время работы алгоритма t примерно оценивается формулой:
                   t=a*N
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.

           6.3. Последовательный поиск в упорядоченном файле

           Если расположить ключи в возрастающем порядке, то время неудачно-
        го поиска можно существенно сократить. В простейшем алгоритме поиска
        в упорядоченном файле поиск прекращается,  если при последовательном
        просмотре  величмна  Х становится больше или равной очередному ключу
        K[i]. В среднем при этом сокращается время неудачного поиска до N/2,
        среднее время удачного поиска остается по-прежнему равным N/2.
           Алгоритм имеет вид:

        ┌───── for i=1 to N ──────────────┐
        │if(X<K[i]) ══>══════════════════>╡
        │if(X=K[i]) Конец: поиск удачен.  │
        │Конец: поиск неудачен            │
        └─────────────────────────────────┘
           Время работы алгоритма t примерно оценивается формулой:
                   t=a*N
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма и не зависящая для данного алгоритмаот результата
        поиска: удачен-неудачен.

           6.4. Бинарный поиск в упорядоченном файле.

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

        l=1; u=N;
       ┌──────────── while(u>=l) ───────┐
       │i=│(l+u)/2│;                    │
       │  └       ┘                     │
       │if(X<K[i]]  u=i-1; ══════>══════╡
       │if(X>K[i]]  l=i+1; ══════>══════╡
       │if(X=K[i]]  Конец: поиск удачен.│
       └────────────────────────────────┘
        Конец: поиск неудачен.

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*lgN
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.
        Лучших результатов не может дать ни один метод,  основанный на срав-
        нении ключей, появляющихся с равной вероятностью.Однако, метод пред-
        назначен только для поиска, как и все методы, основанные на структу-
        ре исходного файла в виде  последовательного  списка.  При включении
        новых ключей очевидны большие затраты по пересылке элементов.

           6.5. Однородный бинарный поиск

           Эта модификация бинарного поиска требует сохранения таблицы значений
        величин D[1] ... D[max] max= │lgN│+2. Эти величины  отражают  возможное
                                     └   ┘
        изменение текущего индекса i на каждом шаге поиска i=i(+-)d,  где d -
        один из элементов массива D. При этом может достигаться экономия времени
        за счет более эффективной программы.
        Схема алгоритма имеет вид.
       ┌────────────────────────────────────────────────────────────────┐
       │                                   j-1    j                     │
       │Сформировать массив D, D[j]=│(N + 2    )/2 │ ,j=1,2,..., │lgN│+2│
       │                            └              ┘             └   ┘  │
       └────────────────────────────────────────────────────────────────┘
        i=D[1]; j=2;
         ╔════════════════════════════════════<══════╗
         ║         ┌────────────────────────────────┐║
        if(X<K[i]] │if(D[j]=0) Конец:поиск неудачен.│║
                   │else i=i-D[j];j=j+1; ══════>════╪╣
                   └────────────────────────────────┘║
                   ┌────────────────────────────────┐║
        if(X>K[i]] │if(D[j]=0) Конец:поиск неудачен.│║
                   │else i=i+D[j];j=j+1; ══════>════╪╝
                   └────────────────────────────────┘
        if(X=K[i]]  Конец: поиск удачен.

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*lgN
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.

           6.6. Интерполяционный поиск

         Алгоритм интерполяционного поиска предполагает, что исходный файл
        упорядочен по величинам ключей поиска. Идея алгоритма состоит в том,
        что делается предположение о равномерном распределении величин в
        некотором их диапазоне от u до l. Поэтому, зная величину Х ключа поиска,
        можно предсказать более точное положение искомой записи, чем просто
        в середине некоторого отрезка файла. Формула нахождения положения
        следующего элемента для сравнения следует из деления длины отрезка
        u-l пропорционально величинам разностей ключей K[u]-K[l] и X-K[l].
        Интерполяционный поик ассимптотически предпочтительнее бинарного, если
        только соблюдается гипотеза о равномерном распределении величин ключей.
           Алгоритм имеет вид:

        l=1; u=N;
        while(u>=l)
       ┌────────────────────────────────────┐
       │ i=l+│(u-l)*(X-K[l])/(K[u]-K[l])│   │
       │     └                          ┘   │
       │if(X<K[i]]  u=i-1; ══════>══════════╡
       │if(X>K[i]]  l=i+1; ══════>══════════╡
       │if(X=K[i]]  Конец: поиск удачен.    │
       └────────────────────────────────────┘
        Конец: поиск неудачен

           Время работы алгоритма t примерно оценивается формулой:
                   t=a*lgN
        где a - неизвестная константа, зависящая от программной реализа-
        ции алгоритма, а также от результата поиска: удачен-неудачен.
