Інтерполяційний алгоритм пошуку

Інтерполяційний алгоритм пошуку — алгоритм для пошуку за заданим ключем в індексованому масиві, який впорядкований за значенням ключів. Це схоже до того, як люди шукають певне ім'я в телефонній книзі. На кожному кроці обчислюється, в якому полі пошуку може бути елемент, базуючись на граничних значеннях цього поля і ключі шуканого елемента, зазвичай за допомогою лінійної інтерполяції. Ключ на вибраній позиції порівнюється з шуканим ключем і, якщо вони не рівні, то залежно від результату порівняння, простір пошуку зводиться до частини до або після даного ключа. Цей метод працюватиме тільки в тому випадку, коли порівняння між ключами є розумним.

До прикладу, двійковий пошук завжди вибирає середину в даному полі пошуку і відкидає одну з половин, порівнюючи значення середини з шуканим. А лінійний пошук порівнює всі елементи один за одним, ігноруючи впорядкованість.

В середньому інтерполяційний пошук робить log(log(n)) порівнянь(якщо елементи є рівномірно розприділеними), де n- кількість елементів. В найгіршому випадку їх кількість може виростати до O(n).

Використовуючи нотацію Ландау, продуктивність алгоритму інтерполяції на наборі даних розміру N рівна O(N). Однак, припускаючи рівномірний розподіл даних по шкалі інтерполяції, можна показати, що показник будеO(log log N).^[1][2][3]. Проте, пошук динамічною інтерполяцією можливий в час o(log log n), використовуючи нову структуру даних.^[4]

Практичне виконання інтерполяції пошуку залежить від того, чи зменшена кількість кроків не буде вимагати складних обчислень, необхідних для кожного кроку. Таке може бути корисним для пошуку у великих відсортованих файлах на диску, де кожен крок включає пошук у диску, що є набагато повільнішим, від арифметичної інтерполяції.

Індексовані структури даних, такі як Б-дерево, також зменшують кількість звернень до диска і частіше використовуються для індексації даних на диску, бо вони можуть індексувати багато типів даних і можуть бути оновленими онлайн. Тим не менше інтерполяційний пошук може використовуватись для пошуку у відсортованому але не індексованому наборі даних.

Коли відсортовані ключі у наборі даних є рівномірно розподіленими номерами, лінійна інтерполяція є простою в реалізації та можна знайти індекс дуже близько до шуканої величини З іншого боку, для телефонної книги, відсортованої за іменами, прямий підхід до інтерполяційного пошуку не може бути застосований. Але тут можна застосувати схожий високорівневий принцип: можна визначити позицію ім'я в телефонній книзі використовуючи залежні набори букв в іменах для визначення положення наступного кроку. Деякі реалізації інтерполяційного пошуку можуть не працювати, якщо в наборі є однакові значення ключів. Найпростіша реалізація інтерполяційного пошуку необов'язково вибере потрібний елемент в такому наборі.

Перетворення імен у телефонній книзі не зможе добитися того, щоб кожне ім'я надавало доступ до одного номера і імена мали рівномірний розподіл (крім як сортувати імена і називати їх name #1, name #2, і т. д.), також відомо, що деякі імена зустрічаються набагато частіше, ніж інші. Така ж ситуація зі словниками, де є багато наборів букв, з яких починається набагато більше слів, ніж з інших. Багато видавців ідуть на значні зусилля, навіть на розрізання одного краю, щоб була можливою усна інтерполяція з першого погляду.

Найпростіша реалізація на С++. На кожній стадії, тут вираховується позиція і потім, як і в двійковому пошуку, рухається або вище, або нижче цієї позиції. На відміну від двійкового пошуку, гарантій щодо розміру інтервалу на кожному кроці немає ніяких, тому в найгіршому випадку виходить O(n). Варто відмітити, що ця реалізація передбачає, що масив відсортований у зростанні. Якщо навпаки, в цій реалізації виникнуть помилки.

 template <typename T>
int interpolation_search (T * arr, int size, T key)
{
    
    if ( size < 0 || ! arr )         // not the best way to handle this case, but it 
         return -1 ;                 // serves to draw attention to it possibly happening. 


    unsigned long long low = 0 ;
    unsigned long long high = size - 1 ; 
    unsigned long long mid ; 


    while ( ! (arr [high] == arr [low] || key < arr [low] || arr [high] < key)  )  
    {
            mid = low + (key - arr [low]) * ((high - low) / ( arr [high] - arr [low])) ;

            if ( arr [mid] < key ) 
                 low = mid + 1 ;                                    

            else if ( key < arr [mid] )  
                      high = mid - 1 ;
                                
            else return mid ;		     
    } 

    if ( key == arr [low] )  
         return low ;

    else return -1 ;  
             
}

Кожна ітерація в коді вимагає від 5 до 6 порівнянь(додаткове для розрізняння трьох станів < > і =), плюс деяку «брудну» арифметику, коли двійковий пошук можна написати з одним порівнянням і цілочисельною арифметикою на ітерації. Бінарний пошук дозволи би знайти елемент у масиві з мільйона елементів не більше, ніж за двадцять порівнянь, проте інтерполяційний пошук, такий як реалізовано вище дозволить зробити це максимум в три ітерації.

• Двійковий пошук
• Хеш-таблиця

• Interpolation search [Архівовано 4 лютого 2012 у Wayback Machine.]
• National Institute of Standards and Technology [Архівовано 22 січня 2009 у Wayback Machine.]
• Interpolation Search — A Log LogN Search [Архівовано 1 липня 2015 у Wayback Machine.]