Алгоритм

Первоначально в качестве границ - левой и правой берутся значения 1 и n. Пусть p и q обозначают левую и правую границы, тогда p: = 1, а q: = n; далее производится деление и шаг за шагом границы сближаются. Процесс деления должен продолжаться до совпадения границ, когда p = q (т. е. цикл выполняется пока Границы сближаются следующим образом: пусть s - номер среднего элемента, значение s - это целая часть среднего арифметического границ p и q

если тогда надо изменить прежнюю нижнюю границу на а верхняя граница (q) остается без изменения (выбирается правая часть массива), иначе, оставить без изменения нижнюю границу (p), а верхнюю заменить на s

Теперь можно записать этот алгоритм в виде последовательности операторов:

p: = 1; q: = n;

while p < q do

Begin

s: = (p + q) div 2;

if a[s] < b then p: = s + 1 else q: = s

end;

Может случиться, что элемента массива, равного заданному числу b в массиве нет. Это обстоятельство надо учесть и добавить следующие операторы

if a[p] = b then writeln('Число ', b, ' входит в масс. и равно ', p, '-му элементу')

else writeln('Такого элемента в массиве нет')

Program Problem8;

uses WinCrt;

const

n = 20;

type

t = array [1..n] of integer;

var

a: t;

p, q, s, b, i: integer;

begin

writeln('Вводите элементы упорядоченного по неубыванию массива');

for i: = 1 to n do

begin

write('Введите ', i, '-й элемент '); readln(a[i])

end;

writeln;

write('Введите число b '); readln(b);

p: = 1; q: = n;

while p < q do

begin

s: = (p + q) div 2;

if a[s] < b then p: = s + 1

else q: = s

end;

if a[p ]= b

then writeln('Число ', b, ' равно ', p, '-му элементу')

else writeln('Такого элемента в массиве нет')

end.

Задача 9. Поиск " среднего " элемента массива