62. Массивы 63. Алгоритмы обработки массивов

• Название: 62. Массивы 63. Алгоритмы обработки массивов
• Дата: 28.04.2023
• Размер: 1.09 Mb.
• Имя файла: programmirovanie-na-yazyke-python.pptx
• Тип: Документы; #1095573
• страница: 10 из 16

Двоичный поиск

A[0]						A[N-1]	A[N]
6	34	44	55	67	78	82

L

R

с

6

34

44

55

67

78

82

L

с

R

X = 44

6

34

44

55

67

78

82

L

с

R

6

34

44

55

67

78

82

L

R

L = R-1 : поиск завершен!

!

Двоичный поиск

L = 0; R = N # начальный отрезок

while L < R-1:

c = (L+R) // 2 # нашли середину

if X < A[c]: # сжатие отрезка

R = c

else: L = c

if A[L] == X:

print ( "A[", L, "]=", X, sep = "" )

else:

print ( "Не нашли!" )

Двоичный поиск

N	линейный поиск	двоичный поиск
2	2	2
16	16	5
1024	1024	11
1048576	1048576	21

• скорость выше, чем при линейном поиске

• нужна предварительная сортировка

Когда нужно применять?

?

Число сравнений:

Задачи

«A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.

Пример:_Массив:_1_4_7_3_9_2_4_5_2_После_сортировки:_1_2_2_3_4_4_5_7_9_Введите_число_X:_4'>Пример:_Массив:_1_4_7_3_9_2_4_5_2_После_сортировки:_1_2_2_3_4_4_5_7_9_Введите_число_X:_2'>Пример:

Массив:

1 4 7 3 9 2 4 5 2

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

1 2 2 3 4 4 5 7 9

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

2

Число 2 найдено.

Количество сравнений: 2

Задачи

«B»: Заполнить массив случайными числами и отсортировать его. Ввести число 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 не встречается.

Задачи

«C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

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

1 2 2 3 4 4 5 12 19

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

12

Число 12 найдено.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

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

1 2 2 3 4 4 5 12 19

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

11

Число 11 не найдено. Ближайшее число 12.