Zoeken…
Binaire zoekopdracht
Invoering
Binair zoeken is een zoek- en verdeelalgoritme. Het gebruikt O(log n) tijd om de locatie van een element in een zoekruimte te vinden waarbij n de grootte van de zoekruimte is.
Binair zoeken werkt door de zoekruimte bij elke iteratie te halveren na vergelijking van de doelwaarde met de middelste waarde van de zoekruimte.
Als u Binair zoeken wilt gebruiken, moet de zoekruimte op een bepaalde manier worden gesorteerd (gesorteerd). Dubbele vermeldingen (die volgens de vergelijkingsfunctie gelijk zijn) kunnen niet worden onderscheiden, hoewel ze de eigenschap Binair zoeken niet schenden.
Gewoonlijk gebruiken we minder dan (<) als vergelijkingsfunctie. Als een <b, zal het waar terugkeren. als a niet minder is dan b en b niet minder is dan a, zijn a en b gelijk.
Voorbeeldvraag
Je bent een econoom, een behoorlijk slechte hoor. U krijgt de taak om de evenwichtsprijs (dat wil zeggen de prijs waarbij aanbod = vraag) voor rijst te vinden.
Vergeet niet dat hoe hoger een prijs is ingesteld, hoe groter het aanbod en hoe kleiner de vraag
Aangezien uw bedrijf zeer efficiënt is in het berekenen van marktkrachten, kunt u onmiddellijk vraag en aanbod in eenheden rijst krijgen wanneer de prijs van rijst op een bepaalde prijs wordt ingesteld p .
Je baas wil zo snel mogelijk de evenwichtsprijs, maar vertelt je dat de evenwichtsprijs een positief geheel getal kan zijn dat maximaal 10^17 en dat er gegarandeerd precies 1 positieve geheel getaloplossing in het bereik is. Begin dus met je werk voordat je het verliest!
U mag de functies getSupply(k) en getDemand(k) , die precies doen wat in het probleem staat.
Voorbeeld uitleg
Hier is onze zoekruimte van 1 tot 10^17 . Een lineair zoeken is dus onhaalbaar.
Merk echter op dat naarmate de k stijgt, getSupply(k) toeneemt en getDemand(k) afneemt. Dus voor elke x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Daarom is deze zoekruimte monotoon en kunnen we Binair zoeken gebruiken.
De volgende psuedocode toont het gebruik van Binary Search:
high = 100000000000000000 <- Upper bound of search space
low = 1 <- Lower bound of search space
while high - low > 1
mid = (high + low) / 2 <- Take the middle value
supply = getSupply(mid)
demand = getDemand(mid)
if supply > demand
high = mid <- Solution is in lower half of search space
else if demand > supply
low = mid <- Solution is in upper half of search space
else <- supply==demand condition
return mid <- Found solution
Dit algoritme wordt uitgevoerd in ~O(log 10^17) tijd. Dit kan worden gegeneraliseerd tot ~O(log S) tijd waarbij S de grootte van de zoekruimte is, omdat we bij elke iteratie van de while lus de zoekruimte hebben gehalveerd ( van [low: high] naar ofwel [low: mid] of [midden: hoog] ).
C Implementatie van binair zoeken met recursie
int binsearch(int a[], int x, int low, int high) {
int mid;
if (low > high)
return -1;
mid = (low + high) / 2;
if (x == a[mid]) {
return (mid);
} else
if (x < a[mid]) {
binsearch(a, x, low, mid - 1);
} else {
binsearch(a, x, mid + 1, high);
}
}
Binair zoeken: op gesorteerde nummers
Het is het gemakkelijkst om een binaire zoekopdracht op getallen te tonen met behulp van pseudocode
int array[1000] = { sorted list of numbers };
int N = 100; // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for
low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found
Probeer niet vroeg terug te keren door array [mid] te vergelijken met x voor gelijkheid. De extra vergelijking kan de code alleen maar vertragen. Merk op dat je er een te laag moet toevoegen om te voorkomen dat je vast komt te zitten door gehele getallen die altijd naar beneden afronden.
Interessant is dat je met de bovenstaande versie van binair zoeken het kleinste voorkomen van x in de array kunt vinden. Als de array duplicaten van x bevat, kan het algoritme enigszins worden aangepast om het grootste aantal x te retourneren door eenvoudigweg toe te voegen aan de if-voorwaarde:
while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}
Merk op dat in plaats van mid = (low + high) / 2 , het ook een goed idee kan zijn om mid = low + ((high - low) / 2) te proberen voor implementaties zoals Java-implementaties om het risico op het krijgen van een overloop voor echt grote ingangen.
Lineair zoeken
Lineair zoeken is een eenvoudig algoritme. Het loopt door items totdat de zoekopdracht is gevonden, waardoor het een lineair algoritme is - de complexiteit is O (n), waarbij n het aantal items is dat moet worden doorlopen.
Waarom O (n)? In het ergste geval moet u alle n items doorlopen.
Je kunt het vergelijken met het zoeken naar een boek in een stapel boeken - je doorloopt ze allemaal totdat je het boek vindt dat je zoekt.
Hieronder is een Python-implementatie:
def linear_search(searchable_list, query):
for x in searchable_list:
if query == x:
return True
return False
linear_search(['apple', 'banana', 'carrot', 'fig', 'garlic'], 'fig') #returns True
Rabin Karp
Het Rabin – Karp-algoritme of Karp – Rabin-algoritme is een tekenreekszoekalgoritme dat hashing gebruikt om een van een set patroonreeksen in een tekst te vinden. De gemiddelde en beste case-looptijd is O (n + m) in spatie O ( p), maar de tijd in het slechtste geval is O (nm) waarbij n de lengte van de tekst is en m de lengte van het patroon.
Algoritme-implementatie in Java voor stringovereenkomst
void RabinfindPattern(String text,String pattern){
/*
q a prime number
p hash value for pattern
t hash value for text
d is the number of unique characters in input alphabet
*/
int d=128;
int q=100;
int n=text.length();
int m=pattern.length();
int t=0,p=0;
int h=1;
int i,j;
//hash value calculating function
for (i=0;i<m-1;i++)
h = (h*d)%q;
for (i=0;i<m;i++){
p = (d*p + pattern.charAt(i))%q;
t = (d*t + text.charAt(i))%q;
}
//search for the pattern
for(i=0;i<end-m;i++){
if(p==t){
//if the hash value matches match them character by character
for(j=0;j<m;j++)
if(text.charAt(j+i)!=pattern.charAt(j))
break;
if(j==m && i>=start)
System.out.println("Pattern match found at index "+i);
}
if(i<end-m){
t =(d*(t - text.charAt(i)*h) + text.charAt(i+m))%q;
if(t<0)
t=t+q;
}
}
}
Bij het berekenen van de hash-waarde delen we deze door een priemgetal om botsing te voorkomen. Na het delen door priemgetal zijn de kansen op een botsing kleiner, maar er is nog een kans dat de hash-waarde hetzelfde kan zijn voor twee tekenreeksen, dus wanneer we krijgen een match, we moeten het karakter voor karakter controleren om er zeker van te zijn dat we een goede match hebben.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Dit is om de hash-waarde voor het patroon opnieuw te berekenen, eerst door het meest linkse teken te verwijderen en vervolgens het nieuwe teken uit de tekst toe te voegen.
Analyse van lineair zoeken (slechtste, gemiddelde en beste gevallen)
We kunnen drie cases hebben om een algoritme te analyseren:
Het slechtste geval
Gemiddeld geval
Beste geval
#include <stdio.h> // Linearly search x in arr[]. If x is present then return the index, // otherwise return -1 int search(int arr[], int n, int x) { int i; for (i=0; i<n; i++) { if (arr[i] == x) return i; } return -1; }/ * Stuurprogramma om bovenstaande functies te testen * /
int main() { int arr[] = {1, 10, 30, 15}; int x = 30; int n = sizeof(arr)/sizeof(arr[0]); printf("%d is present at index %d", x, search(arr, n, x)); getchar(); return 0; }
Worst Case Analysis (meestal gedaan)
In het ergste geval berekenen we de bovengrens van de looptijd van een algoritme. We moeten het geval kennen dat ervoor zorgt dat het maximale aantal bewerkingen wordt uitgevoerd. Voor Lineair zoeken gebeurt het ergste geval wanneer het te doorzoeken element (x in de bovenstaande code) niet aanwezig is in de array. Als x niet aanwezig is, vergelijkt de functie search () het één voor één met alle elementen van arr []. Daarom is de tijdcomplexiteit van lineair zoeken in het slechtste geval Θ (n)
Gemiddelde casusanalyse (soms gedaan)
In de gemiddelde analyse nemen we alle mogelijke ingangen en berekenen we de berekeningstijd voor alle ingangen. Som alle berekende waarden op en deel de som door het totale aantal ingangen. We moeten de verdeling van zaken kennen (of voorspellen). Laten we voor het lineaire zoekprobleem aannemen dat alle gevallen uniform verdeeld zijn (inclusief het geval dat x niet in de array aanwezig is). Dus we tellen alle gevallen en delen de som door (n + 1). Hierna volgt de waarde van de gemiddelde complexiteit van de zaaktijd.
Best Case-analyse (Bogus)
In het beste geval berekenen we de ondergrens van de looptijd van een algoritme. We moeten het geval kennen dat ervoor zorgt dat een minimum aantal bewerkingen wordt uitgevoerd. In het lineaire zoekprobleem doet zich het beste geval voor wanneer x op de eerste locatie aanwezig is. Het aantal bewerkingen is in het beste geval constant (niet afhankelijk van n). Dus de tijdcomplexiteit in het beste geval is Θ (1) Meestal voeren we een worst case-analyse uit om algoritmen te analyseren. In de slechtste analyse garanderen we een bovengrens voor de looptijd van een algoritme dat goede informatie is. De gemiddelde case-analyse is in de meeste praktische gevallen niet eenvoudig en wordt zelden gedaan. In de gemiddelde gevalanalyse moeten we de wiskundige verdeling van alle mogelijke invoer kennen (of voorspellen). De Best Case-analyse is nep. Het garanderen van een ondergrens voor een algoritme geeft geen informatie, want in het ergste geval kan een algoritme jaren duren.
Voor sommige algoritmen zijn alle gevallen asymptotisch hetzelfde, dat wil zeggen dat er geen slechtste en beste gevallen zijn. Bijvoorbeeld Sorteren samenvoegen. Sorteerbewerking voert in alle gevallen Θ (nLogn) bewerkingen uit. De meeste andere sorteeralgoritmen hebben slechtste en beste gevallen. In de typische implementatie van Quick Sort (waarbij pivot wordt gekozen als hoekelement) doet zich bijvoorbeeld het ergste voor wanneer de invoerarray al is gesorteerd en het beste gebeurt wanneer de pivotelementen de array altijd in twee helften verdelen. Voor invoegsortering treedt het slechtste geval op wanneer de array omgekeerd wordt gesorteerd en het beste geval wanneer de array in dezelfde volgorde als uitvoer wordt gesorteerd.