Алгоритм бінарного пошуку в упорядкованому масиві

1. Ввести розмір масиву.
2. Ввести елементи масиву та ключ пошуку.
3. Покласти ліву межу масиву рівною одиниці, праву межу — рівною введеній кількості елементів.
   3.1. Якщо ліва межа масиву більше правої, то завершити пошук, вважаючи його безрезультатним, інакше виконати дії, зазначені в пунктах 3.2-3.4.
   3.2. Визначити індекс середнього елемента за наведеною нижче формулою middle = (left + right) div 2.
   3.3. Порівняти ключ пошуку зі значенням середнього елемента. Якщо ці значення збігаються, то завершити пошук, вважаючи його успішним, інакше визначити підмасив, в якому треба продовжити пошук. Для цього перейти до пункту 3.4.
   3.4. Якщо ключ пошуку менше значення середнього елемента, виконати процедуру бінарного пошуку для лівого підмасиву з межами left та middle-1, інакше виконати процедуру бінарного пошуку для правого підмасиву з межами middle+1 та right.
4. Якщо пошук завершено успішно, вивести знайдений елемент та його індекс, інакше вивести повідомлення про безуспішність пошуку.

Цей алгоритм реалізовано програмою ех7_6. Результати роботи програми зображено на рис. 7.5.

Program EX7_6;
var mas: array [1..15] of integer;
i, n: integer;
flag: boolean;
x: integer;
middle: integer;
procedure BinSearch(left, right: integer);
begin
if left> right then flag: =false
else
begin
middle: =(left+right) div 2;
if x< mas[middle] then flag: =true
else if x< mas[middle]
then Binsearch(left, middle-1)
else binsearch(middle+1, right);
end;
end;
begin
writeln('binary search');
writeln('enter number of components');
readln(n);
writeln('enter array');
for i: =1 to n do
read(mas[i]);
writeln('enter value to search');
readln(x);
binsearch(1, n);
if flag then writeln('item=', middle)
else writeln('value not found');
end.

Рис. 7.5. Результати роботи програми ех7_6. Бінарний пошук в упорядкованому масиві

Демонстрація прикладу