5.3.2 Поиск в упорядоченном векторе

Задача. Для заданного целочисленного упорядоченного вектора A длины 200 найти номер элемента, совпадающего с заданным целым X.

Решение. Мы используем здесь метод деления пополам -- дихотомию. Идея метода состоит в следующем. Делим вектор A пополам и сравниваем средний элемент A с X; если они совпадают, то решение найдено и процесс останавливается. Если средний элемент больше, чем X, то в силу упорядоченности A значение X не может содержаться в правой половине A, так что мы можем продолжать процесс, применяя его к левой половине вектора A. Аналогично, если средний элемент меньше, чем X, нужно продолжать поиск значений в правой половине вектора A. Таким образом, процесс поиска определяется соотношениями:

module ПоискВУпорядоченномВекторе;
    const N = 200;
    var A : array N+1 of integer;
          L,R, (*Крайние индексы поля поиска *)
          M, (* Середина поля поиска *)
          X,I : integer;
          НАЙДЕН : boolean;
    begin
          read(X); for I := 1 to N do read(A[I]) end;
          (**)
          L := 1; R := N; НАЙДЕН := False;
          (**)
          while (L <= R) & ~ НАЙДЕН do
                (* Ограничивающее выражение: R-L *)
                (* {*)
                M := (L + R) div 2; НАЙДЕН := (X = A[M]);
                if not НАЙДЕН then (* {(X#A[M]),*)
                    if X $<$ A[M] then R := M - 1 else L := M + 1 end
                end
         end;
(*

*)
    if НАЙДЕН then  writeLn('A[', M, ']=',X)
    else writeLn('Числа' ,X, 'в векторе А нет')
    end
end ПоискВУпорядоченномВекторе.

Цикл в программе рано или поздно закончится, поскольку ширина поля поиска на каждом повторении тела цикла уменьшается по крайней мере на единицу, так что условие L<=R заведомо станет ложным после 200 его повторений. Инвариантом, т.е. промежуточным утверждением, истинным при каждом повторении тела цикла, является утверждение

поэтому если цикл завершится из-за нарушения условия L<=R, то это означает, что в массиве A нет элемента X. Если же цикл завершится из-за истинности переменной НАЙДЕН, то X = A[M].