Wyszukiwanie binarne jest jednym z najprostszych sposobów na znalezienie elementu w tablicy

Dość często programiści, nawet początkujący,twarz, że istnieje zbiór liczb, w których konieczne jest znalezienie określonej liczby. Ta kolekcja nazywa się tablicą. I znaleźć odpowiedni element, istnieje wiele sposobów. Ale najprostszy z nich po prawej może być uznany za wyszukiwanie binarne. Jaka jest metoda? A jak wdrożyć wyszukiwanie binarne? Pascal jest najprostszym medium do zorganizowania takiego programu, więc wykorzystamy go do nauki.

Najpierw przeanalizujemy, jakie są zalety tej metody, abyśmy mogli zrozumieć,

o co chodzi w badaniu tego tematu. Załóżmy, że istnieje tablica o wymiarze co najmniej 100000000 elementów, w której musisz znaleźć konkretną. Oczywiście ten problem można łatwo rozwiązać za pomocą prostego wyszukiwania liniowego, w którym wykorzystamy cykl do porównania pożądanego elementu ze wszystkimi elementami istniejącymi w macierzy. Problem polega na tym, że realizacja tego pomysłu potrwa zbyt długo. W prostym Pascal programu do kilku zabiegów i trzech linii tekstu głównego, nie zauważy, ale kiedy dochodzimy do bardziej lub mniej dużych projektów z dużą liczbą oddziałów i dobrej funkcjonalności, program będzie gotowy do załadowania na zbyt długo. Zwłaszcza w przypadku słabej wydajności komputera. Dlatego istnieje wyszukiwanie binarne, które zmniejsza czas wyszukiwania o co najmniej dwa razy.

Jaka jest więc zasada działania tegometoda? Warto wspomnieć, że wyszukiwanie binarne nie działa w żadnej tablicy, ale tylko w posortowanym zbiorze liczb. Przy każdym kolejnym kroku jest pobierany środkowy element tablicy (odnoszący się do numeru elementu). Jeśli pożądana liczba jest większa od średniej, wówczas wszystko, co jest po lewej, to znaczy mniej niż element przeciętny, może zostać odrzucone i nie jest tam wyszukiwane. I odwrotnie, jeśli mniej niż przeciętnie, pośród liczb po prawej stronie, nie możesz ich szukać. Następnie wybierzemy nowy obszar wyszukiwania, w którym środkowy element całej tablicy będzie pierwszym elementem, a ostatni pozostanie ostatnim. Średnia liczba nowych obszarów będzie równa ¼ całego segmentu, czyli (ostatni element + średni element całej tablicy) / 2. Ponownie wykonuje się tę samą operację - porównanie ze średnią liczbą tablic. Jeśli pożądana wartość jest mniejsza od średniej, odrzuć prawą stronę i wykonaj to samo, aż do znalezienia tego środkowego elementu.

Oczywiście najlepiej jest przyjrzeć się przykładowi, w jaki napisane jest wyszukiwanie binarne. Tutaj Pascal jest odpowiedni dla każdego - wersja nie jest ważna. Napiszmy prosty program.

Będzie mieć tablicę od 1 do h nazwaną"massiv", zmienna oznaczająca dolną granicę wyszukiwania, zwana "niz", górna granica o nazwie "verh", środkowy element wyszukiwania to "sredn"; a wymaganą liczbą jest "isk".

Tak więc najpierw przypisz górną i dolną granicę przedziału wyszukiwania:

niz: = 1;
verh: = h + 1;

Następnie organizujemy cykl ", podczas gdy dno jest mniejsze niż górny limit":

Podczas gdy niz <verh - 1 do
zacząć

W każdym kroku podziel segment przez 2:

sredn: = (niz + verh) div 2; {używaj funkcji div, ponieważ dzielimy się bez równowagi}

Za każdym razem, gdy sprawdzamy. Jeśli średnia jest równa wymaganej, przerywamy cykl, ponieważ znaleziono już potrzebny element:

jeśli sredn = isk, to przerwij;

Jeśli środkowy element tablicy jest większy od pożądanego, odrzuć lewą stronę, czyli środkowy element zostanie ustawiony jako górna granica:

jeśli massiv [sredn]> isk to verh: = sredn;

A jeśli wręcz przeciwnie, zrobimy z niego niższą granicę:

else niz: = sredn;
koniec;

To wszystko, co będzie w programie.

Przeanalizujmy, jak w praktyce będzie wyglądała metoda binarna. Weźmy następującą tablicę: 1, 3, 5, 7, 10, 12, 18 i szukamy w niej liczby 12.

Łącznie mamy 7 elementów, więc średnia będzie czwartą, a jej wartość 7.

Ponieważ 12 jest większe niż 7, możemy odrzucić elementy 1.3 i 5. Następnie mamy 4 cyfry w lewo, 4/2 bez balansu 2. W związku z tym nowy środkowy element będzie wynosił 10.

Ponieważ 12 jest większe niż 10, odrzucamy 7. Pozostaje tylko 10, 12 i 18.

Tutaj środkowy element ma już 12, jest to pożądana liczba. Zadanie zakończone - znaleziono numer 12.