Заполнить массив случайными числами и отсортировать его. Ввести число X.

Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

4

Число 4 встречается 2 раз (а).

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

14

Число 14 не встречается.

Question

Информатика

Стеха

20 января, 12:52

Заполнить массив случайными числами и отсортировать его. Ввести число X.

Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

4

Число 4 встречается 2 раз (а).

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

Введите число X:

14

Число 14 не встречается.

+2

Ответы (1)

Знаете ответ?

Витяхя · Answer 1

Добавьте двоичный поиск для поиска элемента массива, равного x.

{ двоичный поиск }

{ l - левая граница для поиска }

{ r - правая граница для поиска }

l:=1;

r:=n;

while true do

begin

i: = (l+r) div 2;

if a[i]=x then break;

if a[i]>x then r:=i

else if a[l]
end;

k:=0;

for i:=l to r do

if a[i]=x then k:=k+1;

{ конец двоичного поиска }