Interpolacijsko pretraživanje na Javi
1. Uvod
U ovom uputstvu proći ćemo kroz algoritme pretraživanja s interpolacijom i razgovarati o njihovim prednostima i nedostacima. Nadalje, implementirat ćemo ga u Javu i razgovarati o vremenskoj složenosti algoritma.
2. Motivacija
Interpolacijsko pretraživanje poboljšanje je u odnosu na binarno pretraživanje prilagođeno jednoliko distribuiranim podacima.
Binarno pretraživanje prepolovljuje prostor za pretraživanje na svakom koraku bez obzira na distribuciju podataka, stoga je vremenska složenost uvijek O (log (n)).
S druge strane, Složenost interpolacijskog vremena pretraživanja varira ovisno o distribuciji podataka. Brže je od binarnog pretraživanja jednoliko distribuiranih podataka s vremenskom složenošću O (log (log (n))). Međutim, u najgorem scenariju može se ponašati loše Na).
3. Interpolacijsko pretraživanje
Slično binarnom pretraživanju, interpolacijsko pretraživanje može raditi samo na razvrstanom nizu. Na svaku iteraciju postavlja sondu u proračunski položaj. Ako je sonda točno na stavci koju tražimo, položaj će se vratiti; u suprotnom, prostor za pretraživanje bit će ograničen na desnu ili lijevu stranu sonde.
Izračun položaja sonde jedina je razlika između binarnog i interpolacijskog pretraživanja.
U binarnom pretraživanju, položaj sonde uvijek je najsrednja stavka preostalog prostora za pretraživanje.
Suprotno tome, interpolacijsko pretraživanje izračunava položaj sonde na temelju ove formule:
Pogledajmo svaki od pojmova:
- sonda: ovom će se parametru dodijeliti novi položaj sonde.
- jeftin: indeks krajnje lijeve stavke u trenutnom prostoru pretraživanja.
- highEnd: indeks krajnje desne stavke u trenutnom prostoru pretraživanja.
- podaci[]: niz koji sadrži izvorni prostor za pretraživanje.
- artikal: predmet koji tražimo.
Da bismo bolje razumjeli kako interpolacijsko pretraživanje funkcionira, pokažimo to na primjeru.
Recimo da želimo pronaći položaj 84 u nizu ispod:
Duljina niza je 8, dakle u početku highEnd = 7 i jeftin = 0 (jer indeks niza počinje od 0, a ne od 1).
U prvom koraku formula položaja sonde rezultirat će u sonda = 5:
Budući da je 84 ( artikal tražimo) veća je od 73 (trenutna sonda stavka položaja), sljedeći će korak dodijeliti lijevu stranu niza jeftin = sonda + 1. Sad se prostor za pretraživanje sastoji od samo 84 i 101. The sonda postavit će se formula položaja sonda = 6 što je točno indeks 84:
Budući da je predmet koji smo tražili pronađen, vratit će se pozicija 6.
4. Implementacija u Javi
Sad kad smo shvatili kako algoritam funkcionira, primijenimo ga na Javi.
Prvo, inicijaliziramo jeftin i highEnd:
int highEnd = (data.length - 1); int lowEnd = 0;
Dalje, postavljamo petlju i u svakoj iteraciji izračunavamo novo sonda na temelju gore spomenute formule. Uvjet petlje osigurava da usporedbom ne izađemo iz prostora za pretraživanje artikal do podaci [lowEnd] i podaci [highEnd]:
while (item> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int sonda = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - podaci [lowEnd]); }
Također provjeravamo jesmo li pronašli predmet nakon svakog novog sonda zadatak.
Napokon se prilagodimo jeftin ili highEnd da biste smanjili prostor za pretraživanje na svakoj iteraciji:
public int interpolationSearch (int [] podaci, int stavka) {int highEnd = (data.length - 1); int lowEnd = 0; while (item> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int sonda = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - podaci [lowEnd]); if (highEnd == lowEnd) {if (data [lowEnd] == item) {return lowEnd; } else {povratak -1; }} if (podaci [sonda] == stavka) {vratiti sondu; } if (podaci [sonda] <stavka) {lowEnd = sonda + 1; } else {highEnd = sonda - 1; }} povratak -1; }
5. Zaključak
U ovom smo članku na primjeru istražili pretragu interpolacije. Primijenili smo ga i na Javi.
Primjeri prikazani u ovom vodiču dostupni su na Githubu.