Wyszukiwanie binarne - algorytm parsowania w c++

W trakcie opracowywania oprogramowanie tablice są używane wszędzie. "Inteligentne" typy danych w nowoczesnym języki programowania, takie jak tablice dynamiczne dają duże możliwości wygodnej pracy z obiektami. Ale algorytmy stojące za pracą z tymi typami danych zostały opracowane u zarania informatyki - w połowie XX wieku. Pierwszy algorytm wyszukiwania binarnego został opublikowany w 1946 roku.

Rozważmy najpopularniejsze algorytmy do pracy z tablicami.

Wyszukiwanie indeksowo-liniowe

Jest to najprostszy algorytm wyszukiwania wartości w tablicy. Wykorzystuje metodę porównania tablicy element po elemencie z wartością kluczową. Generalnie szukamy od lewej do prawej. Stosuje się go, gdy w tablicy jest mało elementów lub gdy lista nie jest uporządkowana. Całkowicie nieefektywne w dużych tablicach, gdzie wyszukiwanie binarne jest powszechnie stosowane. Algorytm działa w następujący sposób:

• Porównaj wartość klucza z wartość elementu tablicy.
• Jeśli wartości są równe, zwracamy otrzymaną wartość.
• Jeśli nie, zwiększamy zmienną pętli o jeden i porównujemy ją z kolejnym elementem tablicy.

Indeks Wyszukiwanie sekwencyjne

Bardziej wydajny sposób na znalezienie wartości w posortowanej tablicy. Ale bardziej wymagający pod względem zasobów.

Wyszukiwanie binarne

Wyszukiwanie binarne to algorytm znajdowania elementu tablicy przez kolejne dzielenie tablicy na pół i porównywanie liczby początkowej z liczbą w środku tablicy. Jeśli wartość ze środka jest mniejsza od wymaganej, przechodzimy do szukania w drugiej części; jeśli jest większa, przechodzimy do szukania w pierwszej części. Ten algorytm jest najszybszy ze wszystkich i działa w następujący sposób:

• Znajdź najpierw wartość obiektu w środku tablicy. Sprawdzenie zgodności z wartością oryginalną.
• Jeśli wartość w środku jest mniejsza od początkowej, kontynuujemy poszukiwania w drugiej połowie, jeśli jest większa, szukamy w pierwszej połowie.
• Jeśli otrzymamy połowę, postępujemy w ten sam sposób: dzielimy przez połowę i porównujemy otrzymaną wartość.

Wyszukiwanie odbywa się tak długo, aż wartość początkowa będzie równa wartości w tablicy. Jeśli tak się nie stanie - wartość ta nie istnieje w tablicy.

Istnieje kilka pułapek, które można napotkać podczas projektowania wyszukiwania binarnego.

Przepełnienie wybranego typu danych

Aby znaleźć wartość w środku tablicy, dodaj wartości z prawej i lewej strony, a następnie podziel przez dwa. To jest:

Środek tablicy = Wartość lewa + (Wartość lewa - Wartość prawa)/2

Istnieje niebezpieczeństwo przepełnienia typu danych podczas wykonywania operacji dodawania. Jeśli tablica zawiera wartości o tak dużym rozmiarze, musimy zastosować różne techniki, aby uniknąć ryzyka. Oto kilka standardowych błędów w rozwoju wyszukiwania binarnego.

Błędy wartości

Lub błąd jednego z nich. Bardzo ważne jest, aby rozważyć następujące opcje:

• Pusta tablica.
• Brak wartości.
• Przekroczenie tablicy.

Wiele instancji

Zauważ, że jeśli w tablicy znajduje się wiele instancji tego samego klucza, program musi znaleźć konkretny (pierwszy, ostatni, obok).

Zbadajmy implementację tego algorytmu w języku programowania C plus. Zauważ, że wyszukiwanie binarne działa tylko z posortowaną tablicą! Jeśli tablica nie jest wstępnie posortowana, wynik obliczeń nie będzie poprawny.

Poniżej znajduje się kod w języku C ++. Najpierw inicjalizowana jest tablica zmiennych całkowitych arr, o rozmiarze dziesięć. Następnie operator cin w pętli for czeka, aż użytkownik wprowadzi dziesięć wartości (ciąg dziesięć).

W linii 20 program czeka na podanie przez użytkownika wartości klucza.

Linie od 29 do 35 są implementacją algorytmu wyszukiwania binarnego. Podczas wykonywania programu do zmiennej mid zapisywana jest wartość elementu środkowego według wzoru:

Środek tablicy (mid) = (wartość lewa (l) + wartość prawa (r))/2

Ciąg

arr[mid]==klucz

Sprawdza, czy wartość środkowa jest równa wartości klucza. Jeśli jest równa, to wartość zmiennej flagowej zmienia się na TRUE, więc problem jest rozwiązany.

Jeśli wartość środkowa jest większa od naszej wartości kluczowej, to prawej stronie (zmiennej r) przypisujemy wartość mid. Jeśli jest odwrotnie, to mid jest przypisany do r.

Ostatni z nich to sprawdzenie flagi zmiennej typu boolean.

Zalety wyszukiwania binarnego

Wyszukiwanie binarne powinno być stosowane, jeśli wymagane jest szybkie działanie programu. A napisanie takiego algorytmu nie będzie trudne nawet dla początkującego programisty. Ale bardzo ważne jest, aby rozważyć wszystkie skrajne przypadki: przekroczenie tablicy, brak poszukiwanej wartości, błąd przepełnienia danych.

Wady

Do poprawnej pracy algorytmu tablica musi być wstępnie posortowana. W języku programowania C++ można skorzystać z gotowej funkcji sort(). I jest jeszcze jedna ważna kwestia, którą należy poruszyć uwaga, nauka wyszukiwania binarnego w C i C++. Ten algorytm może być używany tylko z pewnymi strukturami danych. Na przykład struktury wykorzystujące listy połączone nie będą tutaj działać.