Question

Умоляю с по заполнить массив случайными числами, отсортировать его. ввести х, используя двоичный поиск определить есть ли в массиве число равное х посчитать количество сравнений на языке pascal! с понятным решением без tarray и логических функций!

Answer 1

Const
  n = 20;
var
  a: array[1..n] of integer;
  i,j,k,m,li,ri,mi,s,x: integer;
begin
  Write('Введите ключ поиска (0-49): '); Read(x);
  { заполнить массив значениями }
  Randomize;
  Writeln('Элементы массива');
  for i := 1 to n do
  begin
    a[i] := Random(50);
    Write(a[i]:3);
  end;
  Writeln;
  { сортировка }
  for i := 1 to n-1 do
    for j := 1 to n-i do
      if a[j] > a[j+1] then
      begin s := a[j]; a[j] := a[j+1]; a[j+1] := s end;
  Writeln('Отсортированный по возрастанию массив');
  for i := 1 to n do Write(a[i]:3);
  Writeln;
  { бинарный поиск }
  li:=1; ri:=n; k:=0;
  while li<ri do begin
    mi:=(li+ri) div 2;
    if a[mi]<x then li:=mi+1 else ri:=mi;
    Inc(k)
  end;
  if a[ri]=x then m:=ri else m:=0;
  { вывод результатов }
  if m>0 then Writeln('Найден элемент № ',m,'; число шагов равно ',k)
  else Writeln('Такого элемента в массиве нет');
end.

Тестовое решение:
Введите ключ поиска (0-49): 25
Элементы массива
 33 47  1 28 31 36 15 25 49 35 30 48 24  0 39 35  7 20 25  0
Отсортированный по возрастанию массив
  0  0  1  7 15 20 24 25 25 28 30 31 33 35 35 36 39 47 48 49
Найден элемент № 8; число шагов равно 4

Вариант с процедурами
const
  n = 20;
type
  V=array[1..n] of integer;

procedure SortBySelect(var a:V);
{Сортировка выбором}
var
  i, j, k: integer;
  x: integer;
begin
  for i := 1 to n do
    begin
    k := i;
    x := a[i];
    for j := i+1 to n do
      if a[j]<x then
      begin
        k := j;
        x := a[j]
      end;
      a[k] := a[i];
      a[i] := x
    end
end;
 
procedure BinSearch(var a:V;key:integer;var k,m:integer);
var
  li,ri,mi:integer;
begin
  li:=1; ri:=n; k:=0;
  while li<ri do begin
    mi:=(li+ri) div 2;
    if a[mi]<key then li:=mi+1 else ri:=mi;
    Inc(k)
  end;
  if a[ri]=key then m:=ri else m:=-1
end;

var
  a:V;
  i,k,m,x: integer;
begin
  Write('Введите ключ поиска (0-49): '); Read(x);
  { заполнить массив значениями }
  Randomize;
  Writeln('Элементы массива');
  for i := 1 to n do
  begin
    a[i] := Random(50);
    Write(a[i]:3);
  end;
  Writeln;
  SortBySelect(a); { сортировка выбором }
  Writeln('Отсортированный по возрастанию массив');
  for i := 1 to n do Write(a[i]:3);
  Writeln;
  BinSearch(a,x,k,m); { бинарный поиск }
  if m>0 then Writeln('Найден элемент № ',m,'; число шагов равно ',k)
  else Writeln('Такого элемента в массиве нет');
end.

Тестовое решение:
Введите ключ поиска (0-49): 32
Элементы массива
 46 24 32 32 23 32  4 26 47  4 44  8 39  8 15 39 11 45  5 16
Отсортированный по возрастанию массив
  4  4  5  8  8 11 15 16 23 24 26 32 32 32 39 39 44 45 46 47
Найден элемент № 12; число шагов равно 5