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:

  1. Najgorszy przypadek

  2. Średnia sprawa

  3. 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.

Obliczenia matematyczne

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.



Modified text is an extract of the original Stack Overflow Documentation
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow