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.