algorithm
Badawczy
Szukaj…
Wyszukiwanie binarne
Wprowadzenie
Wyszukiwanie binarne to algorytm wyszukiwania Dziel i rządź. Wykorzystuje czas O(log n) do znalezienia położenia elementu w przestrzeni wyszukiwania, gdzie n jest rozmiarem przestrzeni wyszukiwania.
Wyszukiwanie binarne polega na zmniejszeniu o połowę przestrzeni wyszukiwania przy każdej iteracji po porównaniu wartości docelowej ze średnią wartością przestrzeni wyszukiwania.
Aby użyć wyszukiwania binarnego, przestrzeń wyszukiwania musi być w jakiś sposób uporządkowana (posortowana). Nie można rozróżnić zduplikowanych wpisów (tych, które są porównywane według funkcji porównania), chociaż nie naruszają właściwości wyszukiwania binarnego.
Konwencjonalnie używamy mniej niż (<) jako funkcji porównawczej. Jeśli a <b, zwróci wartość true. jeżeli a jest nie mniejsze niż bib jest nie mniejsze niż a, aib są równe.
Przykładowe pytanie
Jesteś ekonomistą, ale dość kiepskim. Zadanie polega na znalezieniu ceny równowagi (czyli ceny, w której podaż = popyt) ryżu.
Pamiętaj, że im wyższa cena, tym większa podaż i niższy popyt
Ponieważ Twoja firma bardzo skutecznie oblicza siły rynkowe, możesz natychmiast uzyskać podaż i popyt w jednostkach ryżu, gdy cena ryżu jest ustalona na określoną cenę p .
Twój szef chce jak najszybciej ceny równowagi, ale mówi ci, że cena równowagi może być dodatnią liczbą całkowitą, która wynosi co najwyżej 10^17 a gwarantowane jest dokładnie 1 dodatnie rozwiązanie liczby całkowitej w zakresie. Zacznij swoją pracę, zanim ją stracisz!
Możesz wywoływać funkcje getSupply(k) i getDemand(k) , które zrobią dokładnie to, co podano w problemie.
Przykład Objaśnienie
Tutaj nasza przestrzeń wyszukiwania wynosi od 1 do 10^17 . Zatem wyszukiwanie liniowe jest niemożliwe.
Jednak należy zauważyć, że gdy k idzie w górę, getSupply(k) wzrasta i getDemand(k) maleje. Zatem dla dowolnego x > y getSupply(x) - getDemand(x) > getSupply(y) - getDemand(y) . Dlatego ta przestrzeń wyszukiwania jest monotoniczna i możemy korzystać z wyszukiwania binarnego.
Poniższy kod psuedocode demonstruje użycie wyszukiwania binarnego:
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
Algorytm działa w czasie ~O(log 10^17) . Może być uogólnione do ~O(log S) czas, w którym S oznacza rozmiar przestrzeni poszukiwań, ponieważ w każdym iteracji while pętli, to połowę przestrzeni poszukiwań (z [Niski: High] albo [Low mid] lub [mid: high] ).
C Implementacja wyszukiwania binarnego z rekurencją
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);
}
}
Wyszukiwanie binarne: według posortowanych liczb
Najłatwiej jest wyświetlić wyszukiwanie binarne na liczbach za pomocą pseudokodu
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
Nie próbuj wracać wcześniej, porównując tablicę [mid] z x dla równości. Dodatkowe porównanie może jedynie spowolnić kod. Uwaga: musisz dodać jeden do najniższego, aby uniknąć uwięzienia przez dzielenie liczb całkowitych zawsze zaokrąglające w dół.
Co ciekawe, powyższa wersja wyszukiwania binarnego pozwala znaleźć najmniejsze wystąpienie x w tablicy. Jeśli tablica zawiera duplikaty x, algorytm można nieznacznie zmodyfikować, aby zwrócił największe wystąpienie x, po prostu dodając do warunku if:
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;
}
Zauważ, że zamiast robić mid = (low + high) / 2 , dobrym pomysłem może być wypróbowanie mid = low + ((high - low) / 2) dla implementacji takich jak implementacje Java, aby zmniejszyć ryzyko uzyskania przepełnienie dla naprawdę dużych nakładów.
Wyszukiwanie liniowe
Wyszukiwanie liniowe to prosty algorytm. Pętla przechodzi przez elementy, dopóki nie zostanie znalezione zapytanie, co czyni go algorytmem liniowym - złożoność wynosi O (n), gdzie n jest liczbą elementów do przejścia.
Dlaczego O (n)? W najgorszym przypadku musisz przejść przez wszystkie n elementów.
Można to porównać do szukania książki w stosie książek - przeglądasz je wszystkie, aż znajdziesz tę, którą chcesz.
Poniżej znajduje się implementacja języka Python:
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
Algorytm Rabin – Karp lub algorytm Karp – Rabin to algorytm przeszukiwania ciągów, który używa haszowania do znalezienia dowolnego zestawu ciągów wzorców w tekście. Jego średni i najlepszy czas działania to O (n + m) w przestrzeni O ( p), ale jego najgorszym czasem jest O (nm), gdzie n jest długością tekstu, a m jest długością wzoru.
Implementacja algorytmu w java do dopasowywania ciągów
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;
}
}
}
Przy obliczaniu wartości skrótu dzielimy ją przez liczbę pierwszą, aby uniknąć kolizji. Po podzieleniu przez liczbę pierwszą szanse na kolizję będą mniejsze, ale nadal istnieje szansa, że wartość skrótu może być taka sama dla dwóch łańcuchów, więc kiedy otrzymujemy dopasowanie, musimy sprawdzić znak po znaku, aby upewnić się, że mamy prawidłowe dopasowanie.
t = (d * (t - text.charAt (i) * h) + text.charAt (i + m))% q;
Ma to na celu ponowne obliczenie wartości skrótu dla wzorca, najpierw usuwając lewy znak najbardziej, a następnie dodając nowy znak z tekstu.
Analiza wyszukiwania liniowego (najgorsze, średnie i najlepsze przypadki)
Możemy mieć trzy przypadki do analizy algorytmu:
Najgorszy przypadek
Średnia sprawa
Najlepszy przypadek
#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; }/ * Program sterownika do testowania powyższych funkcji * /
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; }
Analiza najgorszego przypadku (zwykle zrobione)
W najgorszym przypadku obliczamy górną granicę czasu działania algorytmu. Musimy znać przypadek, który powoduje wykonanie maksymalnej liczby operacji. W przypadku wyszukiwania liniowego najgorszy przypadek występuje, gdy element do przeszukania (x w powyższym kodzie) nie występuje w tablicy. Gdy x nie jest obecny, funkcje search () porównują go ze wszystkimi elementami arr [] jeden po drugim. Dlatego też najgorszym przypadkiem złożoności wyszukiwania liniowego byłoby Θ (n)
Analiza średnich przypadków (czasami wykonywana)
W analizie średnich przypadków bierzemy wszystkie możliwe dane wejściowe i obliczamy czas obliczeniowy dla wszystkich danych wejściowych. Zsumuj wszystkie obliczone wartości i podziel sumę przez całkowitą liczbę danych wejściowych. Musimy znać (lub przewidywać) rozkład przypadków. W przypadku problemu wyszukiwania liniowego załóżmy, że wszystkie przypadki są równomiernie rozmieszczone (w tym przypadek x nieobecny w tablicy). Sumujemy więc wszystkie przypadki i dzielimy sumę przez (n + 1). Poniżej podano wartość średniej złożoności sprawy.
Analiza najlepszych przypadków (fikcja)
W najlepszej analizie przypadku obliczamy dolną granicę czasu działania algorytmu. Musimy znać przypadek, który powoduje wykonanie minimalnej liczby operacji. W przypadku problemu wyszukiwania liniowego najlepszy przypadek występuje, gdy x jest obecny w pierwszej lokalizacji. Liczba operacji w najlepszym przypadku jest stała (niezależna od n). Zatem złożoność czasu w najlepszym przypadku wynosiłaby Θ (1) W większości przypadków analizujemy algorytmy w najgorszym przypadku. W najgorszej analizie gwarantujemy górną granicę czasu działania algorytmu, który jest dobrą informacją. Analiza przeciętnego przypadku nie jest łatwa do wykonania w większości przypadków praktycznych i rzadko jest przeprowadzana. W analizie średniego przypadku musimy znać (lub przewidywać) rozkład matematyczny wszystkich możliwych danych wejściowych. Analiza najlepszych przypadków jest nieprawdziwa. Gwarantowanie dolnej granicy algorytmu nie zapewnia żadnych informacji, ponieważ w najgorszym przypadku uruchomienie algorytmu może zająć lata.
W przypadku niektórych algorytmów wszystkie przypadki są asymptotycznie takie same, tzn. Nie ma najgorszych i najlepszych przypadków. Na przykład Scal Sortuj. Scal sortowanie wykonuje operacje Θ (nLogn) we wszystkich przypadkach. Większość innych algorytmów sortowania ma najgorsze i najlepsze przypadki. Na przykład w typowej implementacji szybkiego sortowania (gdzie element obrotowy jest wybierany jako element narożny) najgorsze ma miejsce, gdy tablica wejściowa jest już posortowana, a najlepsze występuje, gdy elementy przestawne zawsze dzielą tablicę na dwie połowy. W przypadku sortowania z wstawieniem najgorszy przypadek występuje, gdy tablica jest sortowana odwrotnie, a najlepszy przypadek występuje, gdy tablica jest sortowana w tej samej kolejności co dane wyjściowe.
