Komputery » Wyszukiwanie binarne - analiza algorytmu w C ++

Wyszukiwanie binarne - analiza algorytmu w C ++

Komputery

W rozwoju oprogramowania tablice są używane wszędzie. "Inteligentne" typy danych we współczesnych językach programowania, takie jak dynamiczne tablice, zapewniają ogromne możliwości wygodnej pracy z obiektami. Ale algorytmy leżące u podstaw pracy z tymi typami danych, które powstały u zarania informatyki - w połowie XX wieku. Pierwszy algorytm wyszukiwania binarnego został opublikowany w 1946 roku. Rozważ najpopularniejsze algorytmy obsługi tablic.

Wyszukiwanie sekwencyjne

Jest to najprostszy algorytm znajdowania wartości w tablicy. Używa metody naprzemiennego porównywania elementów tablicy z wartością klucza. Zwykle wykonywane od lewej do prawej. Używane, gdy elementy w tablicy są nieznacznie z listy. Absolutnie nieskuteczne w dużych tablicach, w których zwykle używane są wyszukiwania binarne. Algorytm działa w następujący sposób:


  • Porównaj wartość klucza z wartością elementu tablicy.
  • Jeśli wartości są równe, zwracamy wynikową wartość.
  • Jeśli nie, zwiększamy wartość zmiennej cyklu o jeden i porównujemy z następnym elementem tablicy.

    • Wyszukiwanie według kolejności indeksów

    Bardziej skuteczny sposób wyszukiwania wartości w posortowanej tablicy. Ale bardziej wymagający dla zasobów.

    Wyszukiwanie binarne

    Wyszukiwanie binarne (binarne) jest algorytmem znajdowania elementu tablicy poprzez sekwencyjne dzielenie tablicy na pół i porównywanie wyniku z liczbą z połowy tablicy.Jeśli liczba od środka jest mniejsza od pożądanej, w drugiej części szukamy dalej, jeśli więcej - kontynuujemy wyszukiwanie w pierwszej. Algorytm jest najszybszy ze wszystkich wymienionych i działa w następujący sposób:


  • Najpierw dowiadujemy się o wartości obiektu w środku tablicy. Sprawdź, aby dopasować oryginalną wartość.
  • Jeśli wartość od środka jest mniejsza od oryginału, to kontynuujemy wyszukiwanie w drugiej połowie, jeśli więcej - szukamy pierwszego.
  • W wynikowej połowie postępować w ten sam sposób: podzielić go na pół i porównać uzyskaną wartość.
    • Wyszukiwanie odbywa się do momentu, gdy wartość początkowa stanie się równa wartości w tablicy. Jeśli tak się nie stanie - ta wartość w tablicy nie istnieje.
    Istnieje kilka pułapek, które można napotkać podczas projektowania wyszukiwania binarnego.

    Przepełnienie wybranego typu danych

    Aby znaleźć wartość w środku tablicy, należy wprowadzić prawą i lewą wartość i podzielić przez dwa. To znaczy:Środek tablicy = Wartość lewy + (Wartość lewostronna - Wartość prawidłowa) /2

    Istnieje niebezpieczeństwo przepełnienia typu danych podczas operacji dodawania. Jeśli macierz jest tak duża, musisz użyć różnych technik, aby uniknąć ryzyka. Poniżej znajdują się standardowe błędy podczas projektowania wyszukiwania binarnego.

    Błędy wartości

    Lub pomyłki na jednostkę. Bardzo ważne jest rozważenie następujących opcji:

    • Pusty układ.
    • Brak wartości.
    • Przekroczenie tablicy.

    Wiele kopii

    Należy zauważyć, żeW przypadku istnienia kilku identycznych wystąpień klucza w tablicy, program musi znaleźć określony (pierwszy, ostatni, następny).


    & lt; script type = "text /javascript" & gt;
    zmienna blockSettings2 = {blockID "R-A-271049-5" renderTo "yandex_rtb_R-A-70350-39" asynchroniczny :! 0};
    if (document.cookie.indexOf ("abmatch =") & gt; = 0) blockSettings2.statId = 70350;
    ! Zastosowanie (a, b, c, d, e) {A [c] = A [c] || [] A [c] .Push (funkcja () {Ya.Context.AdvManager.render (blockSettings2)}), e = b.getElementsByTagName ("scenariusz")d = b.createElement ("scenariusz") d.type = "text /JavaScript" d.src = „//an.yandex .ru /System /context.js "d.async = 0e.parentNode.insertBefore (d, e)} (to this.document," yandexContextAsyncCallbacks „);

    Rozważmy implementację tego algorytmu w języku programowania C plus. Zwróć uwagę, że wyszukiwanie binarne działa tylko z posortowaną tablicą! Jeśli tablica nie jest wstępnie posortowana, wynik obliczeń będzie nieprawidłowy.

    Poniżej znajduje się kod w C ++. Początkowo początkowo inicjalizowana jest tablica zmiennych typu arr, o rozmiarze 10. Następnie operator cin in the loop czeka na wprowadzenie dziesięciu wartości od użytkownika (linia dziesięć).

    W dwudziestej linii program oczekuje od użytkownika wprowadzenia wartości klucza.

    Wiersze 29 - 35 reprezentują zaimplementowany algorytm przeszukiwania binarnego. Podczas programu zmiennej średniej rejestrowana wartość przeciętnego o wzorze

    ,

    Bliski tablica (połowa) = (liczba pozostałych (L) + Wartości prawej (R)) /2 ,

    Wiersz

    arr [środek] == kluczSprawdzane jest, czy wartość środkowa jest wartością kluczową. Jeśli tak, wartość flagi flagi zmienia się na PRAWDA, to znaczy problem zostaje rozwiązany. Jeśli mediana jest większa niż wartość naszego klucza, to prawa strona (zmienna r) jest przypisana do połowy. JeśliWręcz przeciwnie, środek umieszcza się w r. Ten ostatni sprawdza flagę flagi binarnej.

    Zalety przeszukiwania binarnego

    Jeśli potrzebujesz szybkiej operacji programu, użyj wyszukiwania binarnego. I napisanie takiego algorytmu nie zaszkodzi nawet początkującym programistom. Ale bardzo ważne jest, aby wziąć pod uwagę wszystkie skrajne przypadki: poza granicami tablicy, brak pożądanej wartości, błąd przepełnienia danych.

    Wady

    W celu poprawnego działania algorytmu tablica musi zostać wstępnie posortowana. Aby to zrobić, możesz użyć gotowej funkcji sort () w języku programowania C ++. I jeszcze jeden ważny punkt, na który warto zwrócić uwagę podczas badania binarnego w C i C ++. Tego algorytmu można używać tylko z pewnymi strukturami danych. Na przykład struktury korzystające z połączonych list nie są tutaj odpowiednie.

    Powiązane publikacje