Основы программирования на С++ для начинающих

Интерполирующий поиск

Угадайте, какое самое любимое занятие многих преподавателей? Подсказываю: Выдумывать в своих классных комнатах страшно академические словечки, чтоб у студентов волосы встали дыбом от мегаулетности его сенсея. Одно из таких коварных словечек, повергающих молодых людей в шок – Интерполяция. Предлагаю осмотреть это чудо математической мысли с самого простейшего ракурса и используя минимум кода, чтоб не мулять глаза тоннами операторов, запутывая себя в теории.

Итак, для начала – что же это за слово такое “Интерполяция”? Интерполяция – это (если говорить на языке студента) определение области поиска, путем вычисления подобия расстояний между искомым значением и всей областью. Помните по геометрии подобие треугольников? Те, у которых одинаковые по значению углы, но пропорции разные. Здесь практически тот же принцип. Вычисляется длина области поиска, и длина от начала области до некоего числа (скажем до центрального элемента в массиве). Вычисление это проводится как с номерами элемента, так и с их значениями, после чего полученная длина области умножается на длину между значениями, и результат прибавленный к значению из начала области дает искомое.

Сложно сразу понять на словах, поэтому попробую показать картинкой:

интерполирующий поиск в с++, c++ для начинающих, алгоритм поиска доклад, курсовая работа

Формула достаточно проста – вычисляется длина между номерами первого элемента и искомого (задаваемого точнее). Такая же длина считается между первым и последним номерами. Длины между собой делятся, как раз и получая вычисление подобия. То же самое происходит со значениями элементов – так же вычисляется расстояние между граничными значениями в массиве. Специально выделяю цветом понятия и связанные с ними части формулы.

Полученная длина номеров элементов массива умножается на длину значений в этих (граничащих) элементах и прибавляется значение в первой ячейке массива.

Получается: 1 + (20-1)/(100-1) * (200-5) = 38 с копейками.

Результат и есть то самое искомое. Т.е. при таких значениях как на картинке в ячейке №20 будет стоять 38. Вот и весь смысл интерполяции – составления подобия между номерами элементов и между значениями элементов.

На С++ это выглядит так:

Таким образом сам цикл просто вычисляет по формуле область массива, где может находиться искомое используя этот самый принцип интерполяции в С++, подбирая подобия так сказать. Если вычисленное не равно искомому, значит нужно сдвинуть границы области, где проходит вычисление.

Если вычисленное больше – сдвигается правая граница области поиска, если меньше – левая. Так отрезая (как в бинарном поиске) кусок массива за куском постепенно достигается нужная ячейка массива, ну или границы области поиска сужаются до таких величин, в пределах которого уже искать нечего, когда дистанция между границами равна 1 (т.е. между точкой А и В нет более элементов для вычисления) решение говорит о том, что значение в массиве не найдено.

Как видите сам цикл не настолько уж и сложен и ужасен. Вся соль то скрыта в его форуме. А остальное – просто проверки: нашли или дальше искать. Вот такая вот она… интерполяция в С++

Интерполяционный поиск в чем-то напоминает двоичный. Только в нем область поиска не делится на две равные части. Вместо этого производится оценка новой области поиска по расстоянию между текущим значением элемента и ключом поиска. Скорость работы интерполирующего поиска превосходит скорость двоичного. Еще одно весомое отличие интерполирующего поиска от двоичного – возможность искать текстовую информацию, а не только числовые значения.

6 thoughts on “Интерполирующий поиск

  1. В коде ошибка : для массива { 52,26,64 ,53, 46, 53, 39, 54, 41, 40, 38 ,53, 38, 45, 32, 29 ,40, 41 } не правильно находит индекс числа 45. Исправляется легко.

  2. Немного улучшил ваш код, так как алгоритм не работал с массивом [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;
    }

  3. В общем, поиск работает только в отсортированном массиве, как в случае и с бинарным поиском. Было бы хорошо, если бы подобная информация указывалась, но всё равно – спасибо за инфу.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *