Wikiszótár

interpolációs keresés

Magyar

Kiejtés

  • IPA: [ ˈintɛrpolaːt͡sijoːʃkɛrɛʃeːʃ]

Főnév

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.


Elméleti leírás

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 [low] és [high] indexek közötti értéktartományban van: - Számítsuk ki az interpolált pozíciót:   - 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 [low, high] tartományban van, az érték nincs a listában.


Pszeudokód

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

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

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

        if arr[pos] == key:
            return pos

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

    return -1

Python implementáció

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

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

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

        if arr[pos] == key:
            return pos

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

    return -1


# Példa használat
arr = [10, 20, 30, 40, 50]
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.")

C++ implementáció

#include <iostream>
using namespace std;

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

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

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

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

        if (arr[pos] < 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[0]);
    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;
}

Összegzés

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=interpolációs_keresés&oldid=3479752”