Используя двоичный поиск, определить есть ли в массиве равное число - Pascal ABC

Узнай цену своей работы

Формулировка задачи:

заполнить массив случайными числами и отсортировать его ввести число x использовать двоичный поиск определить есть ли в массиве равное число х

Решение задачи: «Используя двоичный поиск, определить есть ли в массиве равное число»

textual
Листинг программы
const nmax=100;
var a:array[1..nmax] of integer;
    n,i,j,x,r,l,c:integer;
begin
//создание исходного массива
repeat
write('Введите размер массива от 2 до ',nmax,' n=');
readln(n);
until n in [1..nmax];
writeln('Исходный массив');
for i:=1 to n do
 begin
  a[i]:=1+random(100);
  write(a[i]:4);
 end;
writeln;
//сортировка
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then
 begin
  x:=a[i];
  a[i]:=a[j];
  a[j]:=x;
 end;
//бинарный поиск
write('Введите число для поиска x=');
readln(x);
l:=1;
r:=n;
j:=0;
while (l<=r)and (j=0) do
 begin
   c:=(l+r) div 2;
   if x<a[c] then r:=c-1
   else if x>a[c] then l:=c+1
   else j:=1;
 end;
if j=0 then write('Числа, равного ',x,' в массиве нет')
else write('Число, равное ',x,' в массиве есть')
end.

Объяснение кода листинга программы

  1. Создается переменная nmax, которая определяет максимальное количество элементов в массиве.
  2. Создается переменная a, которая представляет собой массив для хранения целых чисел.
  3. Определяются переменные n, i, j, x, r, l, c, которые будут использоваться в процессе выполнения программы.
  4. Выполняется цикл, который запрашивает у пользователя размер массива от 2 до nmax и сохраняет его в переменной n.
  5. Выполняется цикл, который заполняет массив a случайными числами от 1 до 100.
  6. Выполняется сортировка массива a в порядке возрастания.
  7. Выполняется бинарный поиск числа x в массиве a.
  8. Инициализируются переменные l, r и j для использования в цикле бинарного поиска.
  9. Пока l меньше или равно r и j равно 0, выполняется цикл, который делит массив пополам и проверяет, меньше ли x первого элемента, больше ли x второго или равен x третьему.
  10. Если x меньше первого элемента, то r сдвигается на одну позицию влево.
  11. Если x больше третьего элемента, то l сдвигается на одну позицию вправо.
  12. Если x равен второму элементу, то j сдвигается на одну позицию вправо.
  13. Проверяется, было ли найдено число, равное x.
  14. Если цикл закончился и j равно 0, выводится сообщение о том, что число, равное x, в массиве отсутствует.
  15. Если цикл закончился и j не равно 0, выводится сообщение о том, что число, равное x, в массиве есть.

Оцени полезность:

8   голосов , оценка 3.75 из 5
Похожие ответы