Энциклопедия Turbo Pascal. Главы 1-4
Страница 19. Двоичный поиск

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

     Если данные отсортированы, то может использоваться очень хо-
роший метод поиска,  названный двоичным поиском. При таком поиске
используется  метод  "разделяй и властвуй".  Сначала производится
проверка среднего элемента. Если его ключ больше ключа требуемого
элемента,  то  делается  проверка для среднего элемента из первой
половины.  В противном случае делается проверка среднего элемента
из второй половины.  Этот процесс повторяется до тех пор, пока не
будет найден требуемый элемент или не будет больше  элементов для
проверки.
     Например, для поиска числа 4 в массиве 1 2 3 4 5  6  7  8  9
указанным  методом  сначала  делается проверка среднего элемента,
которым является число 5.  Поскольку этот элемент больше 4, поиск
будет продолжен в первой половине массива, т.е. среди чисел
     1 2 3 4 5.  Здесь средним элементом является 3. Это значение
     меньше 4
и поэтому первая половина не будет больше рассматриваться и поиск
продолжается среди чисел
     4 5. На следующем шаге нужный элемент будет найден. При дво-
     ичном поиске число сравнений в худшем случае равно
log n.  Для среднего случая это значение будет несколько лучше, а
в лучшем случае оно равно единице.
     Приводимую ниже функцию,  которая реализует  двоичный  поиск
для символьных массивов, можно использовать для поиска любой про-
извольной структуры данных,  изменив блок сравнения и определение
типа данного "DataItem".
     function BSearch (item: DataArray; count:integer;
                             key:DataItem):integer;
     var
       low, high, mid: integer;
       found:boolean;
     begin
       low:=1; high:=count;
       found:=false;         { не найден }
       while (low<=high) and (not found) do
       begin
         mid:=(low+high) div 2;
         if key<item[mid] then high:=mid-1
         else if key>item[mid] then low:=mid+1
         else found:=true;  { найден }
       end;
       if found then BSearch:=mid
       else BSearch:=0;  { не найден }
     end; { конец поиска }
     В следующей    главе   исследуются   различные   подходы   к
представлению данных, которые в некоторых случаях значительно об-
легчают сортировку и поиск.