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

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

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

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

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

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

Така че, първо присвояваме на горната и долната граница на търсенето на диапазон:

niz: = 1;
verh: = Н + 1;

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

Докато niz започвам

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

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

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

іf sredn = ISK след прекъсване;

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

ако Massiv [sredn]> ISK след verh: = sredn;

И ако напротив, го прави по-ниската граница:

друго 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 намерен.