Interpolatie zoeken in Java
1. Inleiding
In deze tutorial zullen we de zoekalgoritmen voor interpolatie doorlopen en hun voor- en nadelen bespreken. Verder zullen we het in Java implementeren en praten over de tijdcomplexiteit van het algoritme.
2. Motivatie
Interpolatieonderzoek is een verbetering ten opzichte van binair zoeken dat is toegesneden op uniform gedistribueerde gegevens.
Binair zoeken halveert de zoekruimte bij elke stap, ongeacht de gegevensverdeling, dus de tijd is altijd complex O (logboek (n)).
Aan de andere kant, De complexiteit van de interpolatiezoektijd varieert afhankelijk van de gegevensverdeling. Het is sneller dan binair zoeken naar uniform gedistribueerde gegevens met de tijdcomplexiteit van O (log (log (n))). In het ergste geval kan het echter zo slecht presteren als Aan).
3. Interpolatie zoeken
Net als bij binair zoeken, kan interpolatieonderzoek alleen werken op een gesorteerde array. Het plaatst een sonde in een berekende positie bij elke iteratie. Als de sonde precies op het item staat dat we zoeken, wordt de positie geretourneerd; anders wordt de zoekruimte beperkt tot de rechterkant of de linkerkant van de sonde.
De berekening van de sondepositie is het enige verschil tussen binair zoeken en interpolatie zoeken.
Bij binair zoeken is de sondepositie altijd het middelste item van de resterende zoekruimte.
Integendeel, interpolatieonderzoek berekent de sondepositie op basis van deze formule:
Laten we elk van de termen eens bekijken:
- sonde: de nieuwe sondepositie wordt aan deze parameter toegewezen.
- laag einde: de index van het meest linkse item in de huidige zoekruimte.
- hoogwaardig: de index van het meest rechtse item in de huidige zoekruimte.
- gegevens[]: de array met de originele zoekruimte.
- item: het item dat we zoeken.
Laten we het aan de hand van een voorbeeld demonstreren om beter te begrijpen hoe interpolatie zoeken werkt.
Laten we zeggen dat we de positie van 84 in de onderstaande array willen vinden:
De lengte van de array is 8, dus aanvankelijk hoogwaardig = 7 en laag einde = 0 (omdat de index van de array begint bij 0, niet bij 1).
In de eerste stap resulteert de formule van de sondepositie in sonde = 5:
Omdat 84 (de item we zoeken) is groter dan 73 (de huidige sonde position item), zal de volgende stap de linkerkant van de array verlaten door laag einde = sonde + 1. Nu bestaat de zoekruimte uit slechts 84 en 101. De sonde positie formule wordt ingesteld sonde = 6 wat precies de 84's index is:
Aangezien het item dat we zochten is gevonden, wordt positie 6 geretourneerd.
4. Implementatie in Java
Nu we begrepen hoe het algoritme werkt, gaan we het in Java implementeren.
Eerst initialiseren we laag einde en hoogwaardig:
int highEnd = (data.length - 1); int lowEnd = 0;Vervolgens zetten we een lus op en in elke iteratie berekenen we de nieuwe sonde op basis van de bovengenoemde formule. De lusvoorwaarde zorgt ervoor dat we niet uit de zoekruimte komen door te vergelijken item naar data [lowEnd] en data [highEnd]:
while (item> = data [lowEnd] && item <= data [highEnd] && lowEnd <= highEnd) {int probe = lowEnd + (highEnd - lowEnd) * (item - data [lowEnd]) / (data [highEnd] - data [lowEnd]); }We controleren ook of we het item na elke nieuwe hebben gevonden sonde opdracht.
Ten slotte passen we ons aan laag einde of hoogwaardig om de zoekruimte bij elke iteratie te verkleinen:
openbare int interpolationSearch (int [] data, int item) {int highEnd = (data.length - 1); int lowEnd = 0; while (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; } else {return -1; }} if (data [sonde] == item) {retourneer sonde; } if (data [sonde] <item) {lowEnd = sonde + 1; } else {highEnd = sonde - 1; }} return -1; }5. Conclusie
In dit artikel hebben we de interpolatiezoekopdracht onderzocht met een voorbeeld. We hebben het ook in Java geïmplementeerd.
De voorbeelden die in deze tutorial worden getoond, zijn beschikbaar op Github.
