algorithm
Sökande
Sök…
Binär sökning
Introduktion
Binary Search är en algoritm för Divide and Conquer. Den använder O(log n) tid för att hitta platsen för ett element i ett sökutrymme där n är storleken på sökutrymmet.
Binary Search fungerar genom att halvera sökutrymmet vid varje iteration efter att jämföra målvärdet med mittvärdet i sökutrymmet.
För att använda Binary Search måste sökutrymmet beställas (sorteras) på något sätt. Duplicera poster (de som jämförs lika enligt jämförelsefunktionen) kan inte skiljas, även om de inte bryter mot egenskapen Binary Search.
Konventionellt använder vi mindre än (<) som jämförelsefunktion. Om a <b kommer det att gälla. om a inte är mindre än b och b inte är mindre än a, är a och b lika.
Exempelfråga
Du är en ekonom, men ganska dålig. Du får uppgiften att hitta jämviktspriset (det vill säga priset där utbudet = efterfrågan) på ris.
Kom ihåg att ju högre priset ställs in, desto större utbud och mindre efterfrågan
Eftersom ditt företag är mycket effektivt när det gäller att beräkna marknadskrafterna kan du direkt få tillgång och efterfrågan i risenheter när rispriset är fastställt till ett visst pris p .
Din chef vill ha jämviktspriset ASAP, men säger till dig att jämviktspriset kan vara ett positivt heltal som är högst 10^17 och det finns garanterat exakt en positiv heltalslösning i intervallet. Så gå igång med ditt jobb innan du tappar det!
Du får ringa funktioner getSupply(k) och getDemand(k) , som gör exakt vad som anges i problemet.
Exempel Förklaring
Här är vårt sökutrymme från 1 till 10^17 . Således är en linjär sökning omöjlig.
Observera dock att när k går upp getSupply(k) och getDemand(k) minskar. Således, för alla x > y , getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Därför är detta sökutrymme monotont och vi kan använda Binary Search.
Följande psuedocode visar användningen av 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
Denna algoritm körs i ~O(log 10^17) tid. Detta kan generaliseras till ~O(log S) -tid där S är storleken på sökutrymmet eftersom vi vid varje iteration av while loopen halverade sökutrymmet ( från [låg: hög] till antingen [låg: mitten] eller [mitten: hög] ).
C Implementering av binär sökning med rekursion
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);
}
}
Binär sökning: på sorterade nummer
Det är lättast att visa en binär sökning på siffror med pseudokod
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
Försök inte att återkomma tidigt genom att jämföra matris [mitten] till x för jämlikhet. Den extra jämförelsen kan bara bromsa koden. Observera att du måste lägga till en till låg för att undvika att bli instängd av heltal som alltid avrundas.
Intressant nog, med ovanstående version av binär sökning kan du hitta den minsta förekomsten av x i matrisen. Om matrisen innehåller dubbletter av x, kan algoritmen ändras något för att den ska returnera den största förekomsten av x genom att helt enkelt lägga till i if villkorat:
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;
}
Observera att istället för att göra mid = (low + high) / 2 , kan det också vara en bra idé att prova mid = low + ((high - low) / 2) för implementationer som Java-implementeringar för att minska risken för att få en överflöd för riktigt stora ingångar.
Linjär sökning
Linjär sökning är en enkel algoritm. Det kretsar genom objekt tills frågan har hittats, vilket gör det till en linjär algoritm - komplexiteten är O (n), där n är antalet objekt som ska gå igenom.
Varför O (n)? I värsta fall måste du gå igenom alla n-artiklarna.
Det kan jämföras med att leta efter en bok i en bunt med böcker - du går igenom dem alla tills du hittar den du vill ha.
Nedan följer en Python-implementering:
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
Rabin-Karp-algoritmen eller Karp – Rabin-algoritmen är en strängsökande algoritm som använder hashing för att hitta någon av en uppsättning mönstersträngar i en text. Den genomsnittliga och bästa fallet är O (n + m) i rymden O ( p), men dess värsta fall är O (nm) där n är textens längd och m är längden på mönstret.
Algoritmimplementering i java för strängmatchning
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;
}
}
}
När vi beräknar hashvärde delar vi det med ett primtal för att undvika kollision. Efter att divideras med primtal är chanserna för kollision mindre, men det finns fortfarande en chans att hashvärdet kan vara samma för två strängar, så när vi får en matchning vi måste kontrollera den karaktär för karaktär för att se till att vi har rätt matchning.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Detta är för att beräkna hashvärdet för mönstret först genom att ta bort det vänstra tecknet och sedan lägga till det nya tecknet från texten.
Analys av linjär sökning (värsta, genomsnittliga och bästa fall)
Vi kan ha tre fall för att analysera en algoritm:
Värsta fall
Genomsnittligt fall
Bästa fall
#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; }/ * Driverprogram för att testa funktionerna ovan * /
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; }
Värsta fallanalys (vanligtvis gjort)
I värsta fall beräknar vi den övre gränsen för drifttiden för en algoritm. Vi måste känna till fallet som får maximalt antal operationer att utföras. För Linjär sökning händer det värsta fallet när elementet som ska sökas (x i koden ovan) inte finns i matrisen. När x inte finns, jämför sökfunktionerna () funktionerna med alla elementen i arr [] en efter en. Därför är den värsta fallskomplexiteten för linjär sökning Θ (n)
Genomsnittlig fallanalys (ibland gjort)
I genomsnittlig fallanalys tar vi alla möjliga ingångar och beräknar datortid för alla ingångar. Summa alla beräknade värden och dela summan med det totala antalet ingångar. Vi måste känna till (eller förutse) fördelningen av ärenden. För det linjära sökproblemet, låt oss anta att alla fall är jämnt fördelade (inklusive fallet där x inte finns i matrisen). Så vi summerar alla fall och delar summan med (n + 1). Följande är värdet på den genomsnittliga falltidskomplexiteten.
Bästa fallanalys (bogus)
I bästa fall beräknar vi lägre gräns för drifttiden för en algoritm. Vi måste känna till fallet som gör att minsta antal operationer ska genomföras. I det linjära sökproblemet uppstår det bästa fallet när x är närvarande på den första platsen. Antalet operationer är i bästa fall konstant (inte beroende på n). Så tidskomplexiteten i bästa fall skulle vara Θ (1) De flesta gånger gör vi värsta fallanalys för att analysera algoritmer. I den värsta analysen garanterar vi en övre gräns för drifttiden för en algoritm som är bra information. Den genomsnittliga fallanalysen är inte lätt att göra i de flesta praktiska fall och görs sällan. I den genomsnittliga fallanalysen måste vi veta (eller förutsäga) den matematiska fördelningen av alla möjliga ingångar. Den bästa fallanalysen är falsk. Att garantera en lägre gräns för en algoritm ger inte någon information eftersom i värsta fall kan en algoritm ta flera år att köra.
För vissa algoritmer är alla fall asymptotiskt samma, dvs det finns inga värsta och bästa fall. Till exempel Merge Sort. Merge Sort gör Θ (nLogn) -operationer i alla fall. De flesta av de andra sorteringsalgoritmerna har värsta och bästa fall. Till exempel, i den typiska implementeringen av Quick Sort (där pivot väljs som ett hörnelement), inträffar det värsta när ingångsuppsatsen redan är sorterad och bäst inträffar när pivotelementen alltid delar upp array i två halvor. För insättningssortering inträffar det värsta fallet när matrisen omvändsorteras och det bästa fallet uppstår när matrisen sorteras i samma ordning som utgången.