streamalism.org

1. Introduktion

I denne vejledning gennemgår vi interpolationssøgealgoritmer og diskuterer deres fordele og ulemper. Desuden implementerer vi det i Java og taler om algoritmens tidskompleksitet.

2. Motivation

Interpolationssøgning er en forbedring i forhold til binær søgning skræddersyet til ensartet distribuerede data.

Binær søgning halverer søgerummet på hvert trin uanset datadistribution, så det er altid tidskompleksitet O (log (n)).

På den anden side, interpolationssøgningstidskompleksitet varierer afhængigt af datadistributionen. Det er hurtigere end binær søgning efter ensartet distribuerede data med tidskompleksiteten på O (log (log (n))). I værste fald kan det dog fungere så dårligt som På).

3. Interpolationssøgning

Svarende til binær søgning kan interpolationssøgning kun fungere på et sorteret array. Den placerer en sonde i en beregnet position på hver iteration. Hvis sonden er lige på den vare, vi leder efter, returneres positionen; Ellers vil søgerummet være begrænset til enten højre eller venstre side af sonden.

Sondepositionsberegningen er den eneste forskel mellem binær søgning og interpolationssøgning.

I binær søgning er sondepositionen altid det midterste element i det resterende søgerum.

I modsætning hertil beregner interpolationssøgning probepositionen baseret på denne formel:

Lad os se på hvert af udtrykkene:

• sonde: den nye sondeposition tildeles denne parameter.
• lowEnd: indekset for elementet længst til venstre i det aktuelle søgerum.
• highEnd: indekset for det element, der er længst til højre i det aktuelle søgerum.
• data[]: det matrix, der indeholder det originale søgerum.
• vare: det emne, vi leder efter.

For bedre at forstå, hvordan interpolationssøgning fungerer, lad os demonstrere det med et eksempel.

Lad os sige, at vi vil finde positionen på 84 i nedenstående array:

Arrayets længde er 8, så oprindeligt highEnd = 7 og lowEnd = 0 (fordi matrixindeks starter fra 0, ikke 1).

I det første trin vil probepositionsformlen resultere i sonde = 5:

Fordi 84 (den vare vi leder efter) er større end 73 (den nuværende sonde positionspost), vil næste trin opgive venstre side af arrayet ved at tildele lowEnd = sonde + 1. Nu består søgerummet kun af 84 og 101. sonde position formel vil blive indstillet sonde = 6 hvilket er nøjagtigt 84-indekset:

Da varen, vi ledte efter, blev fundet, returneres position 6.

4. Implementering i Java

Nu hvor vi forstod, hvordan algoritmen fungerer, lad os implementere den i Java.

Først initialiserer vi lowEnd og highEnd:

int highEnd = (data.length - 1); int lowEnd = 0;

Dernæst opretter vi en løkke, og i hver iteration beregner vi den nye sonde baseret på den førnævnte formel. Looptilstanden sørger for, at vi ikke er ude af søgerummet ved at sammenligne vare 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 kontrollerer også, om vi har fundet varen efter hver ny sonde opgave.

Endelig tilpasser vi os lowEnd eller highEnd for at mindske søgerummet for hver iteration:

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; } andet {retur -1; }} hvis (data [probe] == vare) {return probe; } hvis (data [probe] <item) {lowEnd = probe + 1; } andet {highEnd = sonde - 1; }} return -1; }

5. Konklusion

I denne artikel udforskede vi interpolationssøgningen med et eksempel. Vi implementerede det også i Java.

Eksemplerne vist i denne vejledning er tilgængelige på Github.