Доста често програмисти, дори начинаещи,изправени пред факта, че има набор от числа, в които трябва да намерите определено число. Тази колекция се нарича масив. И за да намерите желания елемент в него, има огромно разнообразие от начини. Но най-простият сред тях с право може да се счита за двоично търсене. Какъв е даденият метод? И как да приложим двоично търсене? Pascal е най-лесната среда за организиране на такава програма, така че ще я използваме за проучване.
Първо, ще разгледаме предимствата на този метод, защото можем да разберем
И така, какъв е принципът на товаметод? Струва си да се каже веднага, че двоичното търсене не работи във всеки масив, а само в подреден набор от числа. На всяка следваща стъпка се взима средният елемент от масива (което означава числото на елемента). Ако желаното число е по-голямо от средното, тогава всичко, което е отляво, тоест по-малко от средния елемент, може да бъде изхвърлено и не търсено там. И обратно, ако е по-малко от средното - сред тези числа вдясно, не можете да търсите. След това избираме нова зона за търсене, където първият елемент ще бъде средният елемент на целия масив, а последният ще остане последен. Средният брой на новия регион ще бъде ¼ на целия сегмент, тоест (последният елемент + средният елемент на целия масив) / 2. Отново се извършва същата операция - сравнение със средния брой на масива. Ако желаната стойност е по-малка от средната, изхвърляме дясната страна и правим същото по-нататък, докато не се намери този среден елемент.
Разбира се, най-добре е да погледнете пример как се пише двоично търсене. Pascal е подходящ за всеки тук - версията не е важна. Нека да напишем проста програма.
Той ще има масив от 1 до h, наречен"massiv", променлива, обозначаваща долната граница на търсенето, наречена "niz", горната граница, наречена "verh", средният елемент на търсенето е "sredn"; и номера, който търси ISK.
И така, първо задаваме горната и долната граница на интервала за търсене:
дъно: = 1;
verh: = h + 1;
След това организираме цикъла "докато долната е по-малка от горната граница":
Докато niz
На всяка стъпка разделяме сегмента по 2:
sredn: = (niz + verh) div 2; {използвайте функция div, защото се разделяме без остатък}
Всеки път, когато проверяваме. Ако средната стойност е равна на желаната, прекъсваме цикъла, тъй като необходимия елемент вече е намерен:
иf sredn = isk, тогава прекъснете;
Ако средният елемент на масива е по-голям от желания, изхвърлете лявата страна, тоест присвойте средния елемент към горната граница:
ако massiv [sredn]> isk тогава verh: = sredn;
И ако напротив, тогава го правим долната граница:
else niz: = средно;
край;
Това е всичко, което ще бъде в програмата.
Нека да видим как ще изглежда бинарният метод на практика. Нека вземем масив по този начин: 1, 3, 5, 7, 10, 12, 18 и потърсим числото 12 в него.
Общо имаме 7 елемента, така че средата ще бъде четвъртата, стойността й е 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Тъй като 12 е по-голямо от 7, можем да изхвърлим елементи 1,3 и 5. Тогава ни остават 4 числа, 4/2 без остатък е 2. Значи, новият среден елемент ще бъде 10.
| 7 | 10 | 12 | 18 |
Тук средният елемент е вече 12, това е желаното число. Задачата изпълнена - номер 12 намерен.
