Двоичното търсене е един от най-лесните начини за намиране на елемент в масив

Доста често програмистите, дори начинаещи, се сблъскват с факта, че има набор от номера, в които е необходимо да се намери определен брой. Тази колекция се нарича масив. И за да намерите правилния елемент в него, има много начини. Но най-простият от тях вдясно може да се счита за двоично търсене. Какъв е методът? И как да реализираме двоично търсене? Pascal е най-простият начин за организиране на такава програма, така че ще я използваме за проучване.

Първо, ще анализираме какви са предимствата на този метод, за да можем да разберем, какъв е смисълът в изучаването на тази тема. Така че, нека да има масив с размер от поне 100000000 елементи, които трябва да намерят някои. Разбира се, този проблем може да бъде решен лесно с проста линейна търсене, в което ние сме с помощта на цикъла ще сравни необходимия елемент с всички онези, които са в масива. Проблемът е, че прилагането на тази идея ще отнеме твърде дълго време. В един прост Pascal програма на няколко процедури, и три реда от основния текст, че няма да го забелязват, но когато се стигне до повече или по-малко големи проекти с голям брой клонове и добра функционалност, програмата ще бъде готова да се зареждат твърде дълго. Особено в случай, че компютърът има лоша производителност. Ето защо има двоично търсене, което намалява времето за търсене най-малко два пъти.

И така, какъв е принципът на този метод? Струва си да се отбележи, че двоичното търсене не работи в масив, а само в сортиран набор от номера. При всяка следваща стъпка се взема средният елемент на масива (отнасящ се до номера на елемента). Ако желаете номер повече означава, че всичко, което е отляво, т.е. по-малко от средния елемент, може да бъде изхвърлено и да не бъде претърсено там. Обратно, ако е по-малко от средното сред числата отдясно, не можете да ги търсите. След това ще изберете нова област за търсене, където средният елемент на целия масив ще бъде първият елемент, а последният ще остане последният елемент. Средният брой нови области ще бъде frac14 е общата дължина, т.е. (последният елемент + средния елемент на целия масив) / 2. Отново се изпълнява същата операция - сравнение със средния брой на масива. Ако желаната стойност е по-малка от средната, изхвърлете дясната страна и направете същото докато не се намери този среден елемент.

Разбира се, най-добре е да разгледаме примера за това как е написано двоично търсене. Pascal тук е подходящ за всеки - версията не е важна. Нека да напишем проста програма.

Това е набор от 1 до з под името "Massiv", променлива, показваща по-ниска граница за търсене, наречена "niz", горната граница, наречен "verh", средната търсене термин - "sredn" - и необходимия брой - "ISK".

Затова първо задайте горната и долната граница на интервала за търсене:

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

След това организираме цикъла "докато дъното е по-малко от горната граница":

Докато низ < верх - 1
започвам

На всяка стъпка разделете сегмента с 2:

sredn: = (niz + verh) div 2- {използвайте функцията div, защото разделяме остатъка}

Всеки път, когато провеждаме чек. Ако средната стойност е равна на желаната, прекъсваме цикъла, тъй като вече е намерен желаният елемент:

ако sredn = isk тогава се прекъсне;

Ако средният елемент на масива е по-голям от този, който търсим, изхвърлете лявата страна, т.е. ние приписваме средния елемент на горната граница:

ако масив [sredn]> isk then verh: = sredn;

И ако напротив, ние го правим долната граница:

else niz: = sredn-
приключи;

Това е всичко, което ще бъде в програмата.

Ние ще анализираме как бинарен метод ще изглежда на практика. Ние вземаме такъв масив: 1, 3, 5, 7, 10, 12, 18 и потърсете номер 12 в него.

Общо имаме 7 елемента, така че средната стойност ще бъде четвъртата, нейната стойност 7.

Тъй като 12 е по-голяма от 7, елементите 1,3 и 5 могат да бъдат изхвърлени. След това остават 4 числа, 4/2 без остатъкът е 2. Така че новият среден елемент ще бъде 10.

Тъй като 12 е повече от 10, изхвърлете 7. Само 10, 12 и 18 остават.

Тук средният елемент вече е 12, това е изискуемото число. Задачата е завършена - номер 12 е намерен.