Угадайте, какое самое любимое занятие многих преподавателей? Подсказываю: Выдумывать в своих классных комнатах страшно академические словечки, чтоб у студентов волосы встали дыбом от мегаулетности его сенсея. Одно из таких коварных словечек, повергающих молодых людей в шок – Интерполяция. Предлагаю осмотреть это чудо математической мысли с самого простейшего ракурса и используя минимум кода, чтоб не мулять глаза тоннами операторов, запутывая себя в теории.
Итак, для начала – что же это за слово такое “Интерполяция”? Интерполяция – это (если говорить на языке студента) определение области поиска, путем вычисления подобия расстояний между искомым значением и всей областью. Помните по геометрии подобие треугольников? Те, у которых одинаковые по значению углы, но пропорции разные. Здесь практически тот же принцип. Вычисляется длина области поиска, и длина от начала области до некоего числа (скажем до центрального элемента в массиве). Вычисление это проводится как с номерами элемента, так и с их значениями, после чего полученная длина области умножается на длину между значениями, и результат прибавленный к значению из начала области дает искомое.
Сложно сразу понять на словах, поэтому попробую показать картинкой:
Формула достаточно проста – вычисляется длина между номерами первого элемента и искомого (задаваемого точнее). Такая же длина считается между первым и последним номерами. Длины между собой делятся, как раз и получая вычисление подобия. То же самое происходит со значениями элементов – так же вычисляется расстояние между граничными значениями в массиве. Специально выделяю цветом понятия и связанные с ними части формулы.
Полученная длина номеров элементов массива умножается на длину значений в этих (граничащих) элементах и прибавляется значение в первой ячейке массива.
Получается: 1 + (20-1)/(100-1) * (200-5) = 38 с копейками.
Результат и есть то самое искомое. Т.е. при таких значениях как на картинке в ячейке №20 будет стоять 38. Вот и весь смысл интерполяции – составления подобия между номерами элементов и между значениями элементов.
На С++ это выглядит так:
Таким образом сам цикл просто вычисляет по формуле область массива, где может находиться искомое используя этот самый принцип интерполяции в С++, подбирая подобия так сказать. Если вычисленное не равно искомому, значит нужно сдвинуть границы области, где проходит вычисление.
Если вычисленное больше – сдвигается правая граница области поиска, если меньше – левая. Так отрезая (как в бинарном поиске) кусок массива за куском постепенно достигается нужная ячейка массива, ну или границы области поиска сужаются до таких величин, в пределах которого уже искать нечего, когда дистанция между границами равна 1 (т.е. между точкой А и В нет более элементов для вычисления) решение говорит о том, что значение в массиве не найдено.
Как видите сам цикл не настолько уж и сложен и ужасен. Вся соль то скрыта в его форуме. А остальное – просто проверки: нашли или дальше искать. Вот такая вот она… интерполяция в С++
Интерполяционный поиск в чем-то напоминает двоичный. Только в нем область поиска не делится на две равные части. Вместо этого производится оценка новой области поиска по расстоянию между текущим значением элемента и ключом поиска. Скорость работы интерполирующего поиска превосходит скорость двоичного. Еще одно весомое отличие интерполирующего поиска от двоичного – возможность искать текстовую информацию, а не только числовые значения.
Думаю это одна из тех тем, которая на практике проще чем на словах)
В коде ошибка : для массива { 52,26,64 ,53, 46, 53, 39, 54, 41, 40, 38 ,53, 38, 45, 32, 29 ,40, 41 } не правильно находит индекс числа 45. Исправляется легко.
Естественно, если массив сначала отсортировать по возрастанию.
Двоичный поиск прекрасно ищет текстовую информацию.
Немного улучшил ваш код, так как алгоритм не работал с массивом [0…9] например, тоесть когда a=0,b=количество_елементов – 1.
Нужно просто добавить код
else if (MyArray[x] == WhatFind)
cout << WhatFind << " found in element " << x << endl;
в нужное место.
Изменено:
#include
#include
using namespace std;
#define N 10
int main()
{
int MyArray[N] = {0,1,2,3,4,5,6,7,8,10};
/*for (int i = 0; i < N; i++)
{
MyArray[i] = i;
}*/
int x = 0;
int a = 0;
int b = N-1;
int WhatFind = 10;
bool found;
for (found = false; (MyArray[a] WhatFind) && !found; )
{
x = a + ((WhatFind – MyArray[a]) * (b – a)) / (MyArray[b] – MyArray[a]);
if (MyArray[x] WhatFind)
b = x – 1;
else
found = true;
}
if (MyArray[a] == WhatFind)
cout << WhatFind << " found in element " << a << endl;
else if (MyArray[b] == WhatFind)
cout << WhatFind << " found in element " << b << endl;
else if (MyArray[x] == WhatFind)
cout << WhatFind << " found in element " << x << endl;
else
cout << "Sorry. Not found" << endl;
return 0;
}
В общем, поиск работает только в отсортированном массиве, как в случае и с бинарным поиском. Было бы хорошо, если бы подобная информация указывалась, но всё равно – спасибо за инфу.