Interpolációs keresés Java-ban

1. Bemutatkozás

Ebben az oktatóanyagban bejárjuk az interpolációs keresési algoritmusokat, és megvitatjuk azok előnyeit és hátrányait. Továbbá megvalósítjuk Java-ban, és beszélünk az algoritmus időbeli összetettségéről.

2. Motiváció

Az interpolációs keresés fejlesztés az egyenletesen elosztott adatokra szabott bináris kereséshez képest.

A bináris keresés felezi az egyes lépések keresési terét, függetlenül az adatelosztástól, így mindig bonyolult az idő O (log (n)).

Másrészről, az interpolációs keresési idő összetettsége az adateloszlástól függően változik. Gyorsabb, mint a binárisan keresni az egyenletesen elosztott adatokat az idő bonyolultságával O (log (log (n))). A legrosszabb esetben azonban ugyanolyan gyengén teljesíthet, mint Tovább).

3. Interpolációs keresés

A bináris kereséshez hasonlóan az interpolációs keresés is csak rendezett tömbön működhet. A szondát kiszámított helyzetbe helyezi az egyes iterációkon. Ha a szondának igaza van a keresett elemnél, akkor a pozíció visszaadódik; ellenkező esetben a keresési hely a szonda jobb vagy bal oldalára lesz korlátozva.

A szonda helyzetének kiszámítása az egyetlen különbség a bináris keresés és az interpolációs keresés között.

A bináris keresésben a szonda helyzete mindig a hátralévő keresési hely legközépső eleme.

Ezzel szemben az interpolációs keresés a képlet alapján számítja ki a szonda helyzetét:

Vessünk egy pillantást az egyes kifejezésekre:

  • szonda: ehhez a paraméterhez hozzárendelik az új szonda helyzetét.
  • lowEnd: az aktuális keresési hely bal szélső elemének indexe.
  • highEnd: az aktuális keresési hely jobb szélső elemének indexe.
  • adat[]: az eredeti keresési helyet tartalmazó tömb.
  • tétel: a keresett elem.

Az interpolációs keresés jobb megértése érdekében mutassuk be egy példával.

Tegyük fel, hogy meg akarjuk találni a 84-es pozíciót az alábbi tömbben:

A tömb hossza 8, tehát kezdetben highEnd = 7 és lowEnd = 0 (mert a tömb indexe 0-tól kezdődik, nem pedig 1-től).

Az első lépésben a szonda helyzetének képlete azt eredményezi szonda = 5:

Mert 84 (a tétel keresünk) nagyobb, mint 73 (az áram szonda pozíció elem), a következő lépés hozzárendeléssel elhagyja a tömb bal oldalát lowEnd = szonda + 1. Most a keresési hely csak 84-ből és 101.-ből áll szonda pozíció képlet fog beállni szonda = 6, ami pontosan a 84 indexe:

Mivel a keresett elem megtalálható, a 6. pozíció visszatér.

4. Megvalósítás Java-ban

Most, hogy megértettük az algoritmus működését, valósítsuk meg Java-ban.

Először inicializáljuk lowEnd és highEnd:

int highEnd = (adat.hossz - 1); int lowEnd = 0;

Ezután létrehozunk egy hurkot, és minden egyes iterációban kiszámoljuk az újat szonda a fent említett képlet alapján. A ciklus feltétel biztosítja, hogy összehasonlítással ne kerüljünk ki a keresési térből tétel nak nek adatok [lowEnd] és adatok [highEnd]:

while (elem> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int probe = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - adatok [lowEnd]); }

Azt is ellenőrizzük, hogy minden új után megtaláltuk-e az elemet szonda feladat.

Végül beállítunk lowEnd vagy highEnd az egyes iterációk keresési helyének csökkentése:

public int interpolationSearch (int [] adatok, int elem) {int highEnd = (adat.hossz - 1); int lowEnd = 0; while (elem> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int probe = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - adatok [lowEnd]); if (highEnd == lowEnd) {if (data [lowEnd] == elem) {return lowEnd; } else {return -1; }} if (adat [szonda] == elem) {visszatér szonda; } if (adatok [szonda] <elem) {lowEnd = szonda + 1; } else {highEnd = szonda - 1; }} return -1; }

5. Következtetés

Ebben a cikkben az interpolációs keresést tártuk fel egy példával. Java-ban is megvalósítottuk.

Az oktatóanyagban bemutatott példák elérhetők a Github oldalon.