interpolációs keresés

• IPA:

interpolációs keresés

1. (matematika, algoritmusok) Az interpolációs keresés egy keresési algoritmus, amelyet rendezett (növekvő vagy csökkenő) listákban használunk. Az algoritmus azzal optimalizálja a keresést, hogy nem a középső elemet veszi alapul, mint a bináris keresés, hanem a keresett érték és a lista szélső értékei alapján „interpolálja”, hogy a keresett érték valószínűleg hol helyezkedik el. Ez hasonló ahhoz, ahogyan az emberek egy telefonkönyvben keresnek.

Az interpolációs keresés az alábbi logikát követi:

1. Vegyük a tartomány két szélső indexét: ‘low‘ és ‘high‘.

2. Ha a keresett érték (key) a és indexek közötti értéktartományban van: - Számítsuk ki az interpolált pozíciót: $${\displaystyle pos=low+{\frac {(key-arr)\cdot (high-low)}{arr-arr}}}$$ - Ellenőrizzük az interpolált pozíció értékét:

- Ha az megegyezik a keresett értékkel, térjünk vissza az indexével.

- Ha kisebb, folytassuk a keresést a bal oldali tartományban.

- Ha nagyobb, folytassuk a jobb oldali tartományban.

3. Ha a keresett érték nem a tartományban van, az érték nincs a listában.

function interpolációs_keresés(arr, n, key):
    low = 0
    high = n - 1

    while low <= high and key >= arr and key <= arr:
        if low == high:
            if arr == key:
                return low
            return -1

        pos = low + ((key - arr) * (high - low)) // (arr - arr)

        if arr == key:
            return pos

        if arr < key:
            low = pos + 1
        else:
            high = pos - 1

    return -1

def interpolation_search(arr, key):
    low = 0
    high = len(arr) - 1

    while low <= high and key >= arr and key <= arr:
        if low == high:
            if arr == key:
                return low
            return -1

        pos = low + ((key - arr) * (high - low)) // (arr - arr)

        if arr == key:
            return pos

        if arr < key:
            low = pos + 1
        else:
            high = pos - 1

    return -1


# Példa használat
arr = 
key = 30
result = interpolation_search(arr, key)
if result != -1:
    print(f"A(z) {key} érték megtalálható a(z) {result}. indexen.")
else:
    print(f"A(z) {key} érték nincs a listában.")

#include <iostream>
using namespace std;

int interpolationSearch(int arr, int n, int key) {
    int low = 0, high = n - 1;

    while (low <= high && key >= arr && key <= arr) {
        if (low == high) {
            if (arr == key)
                return low;
            return -1;
        }

        int pos = low + ((key - arr) * (high - low)) / (arr - arr);

        if (arr == key)
            return pos;

        if (arr < key)
            low = pos + 1;
        else
            high = pos - 1;
    }

    return -1;
}

int main() {
    int arr = {10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr);
    int key = 30;

    int result = interpolationSearch(arr, n, key);
    if (result != -1)
        cout << "A(z) " << key << " érték megtalálható a(z) " << result << ". indexen." << endl;
    else
        cout << "A(z) " << key << " érték nincs a listában." << endl;

    return 0;
}

Az interpolációs keresés hatékony, ha a lista értékei egyenletesen oszlanak el, mert ilyenkor az interpolált pozíció pontosabban közelíti a keresett érték helyét. A legrosszabb esetben azonban az időbonyolultsága (O(n)), míg a legjobb esetben (O(n)). Emiatt elsősorban egyenletes eloszlású adatoknál ajánlott használni.

• interpolációs keresés - Értelmező szótár (MEK)
• interpolációs keresés - Etimológiai szótár (UMIL)
• interpolációs keresés - Szótár.net (hu-hu)
• interpolációs keresés - DeepL (hu-de)
• interpolációs keresés - Яндекс (hu-ru)
• interpolációs keresés - Google (hu-en)
• interpolációs keresés - Helyesírási szótár (MTA)
• interpolációs keresés - Wikidata
• interpolációs keresés - Wikipédia (magyar)