Урок на 24 марта Интерполяционный поиск

Тема урока: Интерполяционный поиск

Цель: изучить алгоритм интерполяционного поиска

1. Вопросы для повторения.

   1. Как вы понимаете выражение «поиск информации»?

   2. Какие входные и выходные данные необходимы для поиска?

   3. В чем суть линейного поиска?

   4. Как еще называется линейный поиск?

   5. В каком массиве (отсортированном или нет) выполняется линейный поиск?

   6. В чем суть бинарного поиска?

   7. Какое обязательное условие осуществления бинарного поиска?

2. Новый материал

   1. Прослушайте лекцию https://www.youtube.com/watch?v=DLin2MHqQAw

   2. Запишите в тетрадь основные положения:

      1. Интерполяционный поиск (интерполирующий поиск) основан на принципе поиска в телефонной книге или, например, в словаре. Вместо сравнения каждого элемента с искомым, как при линейном поиске, данный алгоритм производит предсказание местонахождения элемента: поиск происходит подобно двоичному поиску, но вместо деления области поиска на две части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Другими словами, бинарный поиск учитывает лишь знак разности между ключом и текущим значением, а интерполирующий ещё учитывает и модуль этой разности и по данному значению производит предсказание позиции следующего элемента для проверки. В среднем интерполирующий поиск производит log(log(N)) операций, где N есть число элементов, среди которых производится поиск. Число необходимых операций зависит от равномерности распределения значений среди элементов.

      2. Первоначальное сравнение осуществляется на расстоянии шага

,

где

j-номер последнего рассматриваемого элемента,

i-номер первого рассматриваемого элемента,

K-ключ

K_j- значение элемента на позиции J,

K_i- значение элемента на позиции i.

1. Пример:

Дан массив:

2,9.10,12,20,24,28,30,37,40,45,50,51,60,65,70,74,76

Ключ: К=70

Шаг 1. Определим d=[(18-1)*(70-2)/(76-2)]=15

Сравниваем ключ с элементом массива, стоящим на 15 месте.

К₁₅=65

Продолжаем поиск, левую часть массива игнорируем.

Оставшийся массив:

70, 74, 76

Шаг 2. d=[(3-1)*(70-70)/(76-70)]=0

Искомый элемент найден.

1. Вопросы для закрепления.

1. В чем отличие интерполяционного поиска от линейного?

2. В чем отличие интерполяционного поиска от бинарного?

1. Задания.

   1. Записать в тетрадь теоретический материал и пример из лекции.

   2. Привести свой пример для реализации интерполяционного поиска (решить в тетради).

   3. Ответить на вопросы (по видео) :

4.3.1. На чем основан бинарный поиск?

4.3.2 Чем отличается интерполяционный поиск от линейного поиска?

4.3.3 На какой поиск более похож интерполяционный поиск?

4.3.4 От чего зависит число операций в интерполяционном поиске?

4.3.5 Интерполяционный поиск быстрее или медленнее бинарного?