Dość często programiści, nawet początkujący,mają do czynienia z faktem, że istnieje zestaw liczb, w którym konieczne jest znalezienie określonej liczby. Ta kolekcja nazywa się tablicą. A na znalezienie w nim pożądanego elementu jest wiele sposobów. Ale najprostszy z nich można słusznie uznać za wyszukiwanie binarne. Jaka jest ta metoda? A jak zaimplementować wyszukiwanie binarne? Pascal jest najprostszym środowiskiem do zorganizowania takiego programu, więc wykorzystamy go do nauki.
Najpierw przeanalizujemy jakie są zalety tej metody, ponieważ w ten sposób możemy zrozumieć
Jaka jest więc zasada działania tego?metoda? Należy od razu powiedzieć, że wyszukiwanie binarne nie działa w żadnej tablicy, a jedynie w posortowanym zestawie liczb. W każdym kolejnym kroku pobierany jest środkowy element tablicy (czyli numer elementu). Jeśli pożądana liczba jest większa niż średnia, to wszystko, co znajduje się po lewej stronie, czyli mniej niż środkowy element, można tam odrzucić i nie przeszukiwać. I odwrotnie, jeśli jest mniej niż średnia - wśród tych liczb po prawej stronie nie trzeba szukać. Następnie wybierzemy nowy obszar wyszukiwania, w którym pierwszy element będzie środkowym elementem całej tablicy, a ostatni pozostanie ostatnim. Średnia liczba nowego obszaru wyniesie ¼ całego segmentu, czyli (ostatni element + środkowy element całej tablicy) / 2. Ponownie wykonywana jest ta sama operacja - porównanie ze średnią tablicy. Jeśli pożądana wartość jest mniejsza niż średnia, odrzuć prawą stronę i rób to samo dalej, aż ten środkowy element będzie pożądany.
Oczywiście najlepiej przyjrzeć się przykładowi, jak napisane jest wyszukiwanie binarne. Tutaj zrobi każdy Pascal - wersja nie jest ważna. Napiszmy prosty program.
Będzie zawierać tablicę od 1 do h o nazwie„massiv”, zmienna określająca dolną granicę wyszukiwania o nazwie „niz”, górna granica o nazwie „verh”, środkowy termin wyszukiwania o nazwie „sredn”; a wymagana liczba to „isk”.
Tak więc najpierw przypisujemy górną i dolną granicę przedziału wyszukiwania:
niz: = 1;
verh: = h + 1;
Następnie organizujemy cykl „gdy dolna granica jest mniejsza niż górna granica”:
Chociaż niz <verh - 1 do
zaczynać
Na każdym kroku dzielimy segment przez 2:
sredn: = (niz + verh) dział 2; {użyj funkcji div, ponieważ dzielimy bez reszty}
Za każdym razem sprawdzamy. Jeśli średnia jest równa żądanej, przerywamy pętlę, ponieważ wymagany element został już znaleziony:
jeśli sredn = isk to przerwij;
Jeśli środkowy element tablicy jest większy niż pożądany, odrzuć lewą stronę, to znaczy przypisz środkowy element jako górną granicę:
jeśli massiv [sredn]> isk to verh: = sredn;
A jeśli wręcz przeciwnie, to czynimy to dolną granicą:
w przeciwnym razie niz: = sredn;
koniec;
To wszystko, co będzie w programie.
Zobaczmy, jak w praktyce będzie wyglądać metoda binarna. Weźmy taką tablicę: 1, 3, 5, 7, 10, 12, 18 i poszukajmy w niej liczby 12.
W sumie mamy 7 elementów, więc środkowy będzie czwartym, jego wartość to 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Ponieważ 12 jest większe niż 7, możemy odrzucić elementy 1,3 i 5. Pozostały nam 4 liczby, 4/2 bez reszty to 2. Tak więc nowy środkowy element będzie miał wartość 10.
| 7 | 10 | 12 | 18 |
Tutaj środkowy element ma już 12, to jest pożądana liczba. Zadanie wykonane - znaleziono numer 12.
