Бинарното пребарување е еден од најлесните начини да се пронајде елемент во низата

Многу често програмери, дури и почетници, се соочуваат со фактот дека постои збир на броеви во кои е неопходно да се најде одреден број. Оваа збирка се нарекува низа. И да го најдеме вистинскиот елемент во него, постојат многу начини. Но, наједноставниот меѓу нив е бинарното пребарување. Кој е методот? И како да се спроведе бинарно пребарување? Паскал е наједноставната средина за организирање на таква програма, така што ќе ја користиме за студирање.

Прво, ќе анализираме кои се предностите на овој метод, и на крајот на краиштата, за да можеме да разбереме, Која е поентата во проучувањето на оваа тема. Значи, да претпоставиме дека има низа со димензија од најмалку 100000000 елементи, во која треба да пронајдете одредена. Се разбира, овој проблем лесно може да се реши со едноставно линеарно пребарување, во кое ние користиме јамка за да го споредиме посакуваниот елемент со сите оние што постојат во низата. Проблемот е што имплементацијата на оваа идеја ќе потрае премногу време. Во едноставна програма Pascal за неколку процедури и со три реда на главниот текст, нема да го забележите, но кога ќе започнете повеќе или помалку големи проекти со многу разгранување и добра функционалност, завршената програма ќе биде предолго натоварена. Особено ако компјутерот има слаби резултати. Затоа, постои бинарно пребарување, кое го намалува времето за пребарување за најмалку два пати.

Значи, кој е принципот на овој метод? Веднаш вреди да се каже дека бинарното пребарување не работи во било која низа, туку само во сортиран сет на броеви. Во секој следен чекор се зема просечниот елемент од низата (се однесува на бројот на елементот). Ако посакуваниот број е поголем од просекот, тогаш сè што е на лево, што е помалку од просечниот елемент, може да се отфрли и да не се бара таму. Спротивно на тоа, ако е помал од просекот, меѓу броевите на десната страна, не можете да ги барате. Потоа, ќе одбереме нова област за пребарување, каде што средишниот елемент на целата низа ќе биде првиот елемент, а последниот ќе остане последен. Просечниот број на новата област ќе биде ¼ од целиот сегмент, односно (последниот елемент + просечен елемент на целата низа) / 2. Повторно, истата операција се изведува - споредба со просечниот број на низата. Ако посакуваната вредност е помала од просекот, отфрлете ја десната страна и направете го истото додека не се најде овој среден елемент.

Се разбира, најдобриот начин да се погледне на примерот е како да напишете бинарно пребарување. Паскал е погоден за никого - верзијата не е важна. Ајде да напишеме едноставна програма.

Ќе има низа од 1 до h наречена "масив", променлива означува пониска граница за пребарување наречена "niz", горната граница наречена "гор", средниот елемент за пребарување е "sredn"; И потребниот број е "isk".

Значи, прво назначете ги горните и долните граници на интервалот за пребарување:

Niz: = 1;
Верх: = h + 1;

Потоа го организираме циклусот "додека дното е помало од горната граница":

Додека niz Започнете

На секој чекор, дели сегментот за 2:

Sredn: = (niz + verh) div 2; {Користете ја функцијата div бидејќи ние го делиме остатокот}

Секој пат кога проверуваме. Ако просекот е еднаков на саканиот, го прекинуваме циклусот, бидејќи саканиот елемент е веќе пронајден:

Во средно = isk потоа пауза;

Ако средишниот елемент на низата е поголем од оној што го бараме, ја отфрламе левата страна, односно го доделуваме средниот елемент до горната граница:

Ако масив [sredn]> isk тогаш вер: = среден;

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

Друг ред: = среден;
Крај;

Тоа е се што ќе биде во програмата.

Ајде да анализираме како бинарниот метод ќе изгледа во пракса. Земете таква низа: 1, 3, 5, 7, 10, 12, 18 и барајте број 12 во него.

Севкупно, имаме 7 елементи, така што просекот ќе биде четврти, неговата вредност 7.

Бидејќи 12 е поголем од 7, елементите 1,3 и 5 можат да бидат отфрлени. Следно, имаме 4 броеви, 4/2 без остаток е 2. Значи, новиот среден елемент ќе биде 10.

Бидејќи 12 е повеќе од 10, ние ги отфрламе. Само 10, 12 и 18 се оставени.

Тука средишниот елемент е веќе 12, ова е потребниот број. Задачата е завршена - бројот 12 е пронајден.