Программирование на языке Python

Слайд 2

Программирование на языке Python

§ 65. Двоичный поиск

Программирование на языке Python § 65. Двоичный поиск

Слайд 3

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

X = 7

X < 8

8

4

X > 4

6

X > 6

Выбрать средний элемент

Двоичный поиск X = 7 X 8 4 X > 4 6
A[c] и сравнить с X.
Если X == A[c], то нашли (стоп).
Если X < A[c], искать дальше в первой половине.
Если X > A[c], искать дальше во второй половине.

Слайд 4

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

X = 44

Двоичный поиск X = 44

Слайд 5

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

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

Двоичный поиск L = 0; R = N # начальный отрезок while
< 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 ( "Не нашли!" )

Слайд 6

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

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

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

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

Двоичный поиск скорость выше, чем при линейном поиске нужна предварительная сортировка Число сравнений:

Слайд 7

Задачи

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

Задачи «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X.
двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.
Пример:
Массив:
1 4 7 3 9 2 4 5 2
После сортировки:
1 2 2 3 4 4 5 7 9
Введите число X:
2
Число 2 найдено.
Количество сравнений: 2

Слайд 8

Задачи

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

Задачи «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 не встречается.