Interpolasjonssøk i Java
1. Introduksjon
I denne opplæringen vil vi gå gjennom algoritmer for interpolasjonssøking og diskutere fordeler og ulemper med dem. Videre implementerer vi det i Java og snakker om algoritmens tidskompleksitet.
2. Motivasjon
Interpolasjonssøk er en forbedring i forhold til binært søk skreddersydd for jevnt distribuerte data.
Binært søk halverer søkeområdet på hvert trinn uavhengig av datadistribusjon, og det er derfor alltid tidskompleksitet O (logg (n)).
På den andre siden, interpolasjonssøketidskompleksitet varierer avhengig av datadistribusjon. Det er raskere enn binært søk etter jevnt distribuerte data med tidskompleksiteten til O (logg (logg (n))). I verste fall kan det imidlertid fungere så dårlig som På).
3. Interpolasjonssøk
I likhet med binært søk, kan interpolasjonssøk bare fungere på en sortert matrise. Den plasserer en sonde i en beregnet posisjon på hver iterasjon. Hvis sonden er rett på varen vi leter etter, vil stillingen bli returnert; ellers vil søkeområdet være begrenset til høyre eller venstre side av sonden.
Sondeposisjonsberegningen er den eneste forskjellen mellom binært søk og interpolasjonssøk.
I binært søk er soneposisjonen alltid den midterste gjenstanden i det gjenværende søkeområdet.
I motsetning beregner interpolasjonssøk sondeposisjonen basert på denne formelen:
La oss ta en titt på hvert av begrepene:
- sonde: den nye probeposisjonen vil bli tildelt denne parameteren.
- lowEnd: indeksen til det venstre elementet i det gjeldende søkeområdet.
- høyEnd: indeksen til elementet som er lengst til høyre i det gjeldende søkeområdet.
- data[]: matrisen som inneholder det opprinnelige søkeområdet.
- punkt: varen vi leter etter.
For å bedre forstå hvordan interpolasjonssøk fungerer, la oss demonstrere det med et eksempel.
La oss si at vi vil finne posisjonen til 84 i matrisen nedenfor:
Matrisens lengde er 8, så i utgangspunktet highEnd = 7 og lowEnd = 0 (fordi matrisens indeks starter fra 0, ikke 1).
I det første trinnet vil probeposisjonsformelen resultere i sonde = 5:
Fordi 84 ( punkt vi ser etter) er større enn 73 (gjeldende sonde posisjonselement), vil neste trinn forlate matrisen til venstre ved å tilordne lowEnd = sonde + 1. Nå består søkeområdet bare av 84 og 101. sonde posisjonsformel vil angis sonde = 6 som er nøyaktig 84-indeksen:
Siden varen vi lette etter er funnet, vil posisjon 6 bli returnert.
4. Implementering i Java
Nå som vi forsto hvordan algoritmen fungerer, la oss implementere den i Java.
Først initialiserer vi lowEnd og highEnd:
int highEnd = (data.length - 1); int lowEnd = 0;Deretter setter vi opp en løkke og i hver iterasjon beregner vi den nye sonde basert på den nevnte formelen. Sløyfetilstanden sørger for at vi ikke er ute av søkeområdet ved å sammenligne punkt til data [lowEnd] og data [highEnd]:
mens (item> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int probe = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - data [lowEnd]); }Vi sjekker også om vi har funnet varen etter hver nye sonde oppdrag.
Endelig justerer vi lowEnd eller høyEnd for å redusere søkeområdet på hver iterasjon:
public int interpolationSearch (int [] data, int item) {int highEnd = (data.length - 1); int lowEnd = 0; mens (item> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int probe = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - data [lowEnd]); if (highEnd == lowEnd) {if (data [lowEnd] == item) {return lowEnd; } annet {retur -1; }} if (data [probe] == item) {return probe; } hvis (data [probe] <item) {lowEnd = probe + 1; } annet {highEnd = sonde - 1; }} retur -1; }5. Konklusjon
I denne artikkelen undersøkte vi interpolasjonssøket med et eksempel. Vi implementerte det også i Java.
Eksemplene som vises i denne veiledningen, er tilgjengelige på Github.
