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.


$config[zx-auto] not found$config[zx-overlay] not found