Тема algoritmy_binarnogo_poiska LICT 590
Двоично (двоично) търсене (известно още като метод на разполовяване и дихотомия) е класически алгоритъм за намиране на елемент в сортиран масив (вектор). Използва се и за намиране на дадена стойност на монотонна (ненарастваща или ненамаляваща) функция. Търсенето се основава на теоремата за междинната стойност. Използва се в компютърните науки, изчислителната математика и математическото програмиране.
В редица случаи (по-специално при проблеми с интерполация) е необходимо да се установи къде по отношение на даден подреден масив от реални числа се намира дадено реално число. За разлика от търсенето в масив от цели числа, даденото число в този случай най-често не съвпада с нито едно от числата в масива и се изисква да се намерят номерата на елементите, между които това число е затворено.
Един от най-бързите начини за това е двоичното търсене, чийто характерен брой операции е от порядъка на log2(n), където n е броят на елементите на масива. При множество извиквания на тази процедура броят на операциите ще бъде равен на m log2(n) (m е броят на извикванията). Ускоряването на тази процедура може да се постигне чрез запазване на предишния резултат от операцията и опитите за търсене с ново повикване в най-близките възли на масива с допълнително разширяване на зоната за търсене в случай на неуспех.
В този случай в най-лошия случай броят на операциите ще бъде по-голям (около 2 пъти) в сравнение с двоичното търсене, но обикновено, когато m е много по-голямо от log2(n), е възможно да се приведе редът на броя операции до m, тоест да се направи почти независим от размера на масива.
Важен пример за прилагането на такъв алгоритъм е картографирането на област: даден масив от RGB палитра, съответстващ на „нивата“ на картата, оцветете тази област, като определите цвета на всякапиксел. Стойността, съответстваща на пиксела, се счита за дадена (намерена чрез някакъв метод, външен за програмата за оцветяване); той определя между кои нива на картата се намира, а тези числа определят цвета му, получен от палитрата.
Броят на нивата в този случай може да бъде доста голям, докато промяната в нивото между съседните пиксели най-често е слаба. В този случай ускоряването, генерирано от алгоритъма в сравнение със стандартното двоично търсене, е доста значително.
Задачата е поставена така. Даден ви е подреден масив от масив от реални числа с измерение n, стойност за проверка и първоначално приближение на стария възел. Изисква се да се намери номерът на възел res на масива от масив, така че array[res]⇐стойност
Алгоритъмът работи по следния начин.
1. Определя се дали проверената стойност е извън масива array. В случай на valuearray[n-1] се връща n-1.
2. В противен случай се проверява: ако стойността на old е извън индексите на масива (т.е. old = n), тогава преминаваме към обичайното двоично търсене, задавайки лявата граница left=0, дясната граница right=n-1.
3. В противен случай се пристъпва към уточняване на границите на търсенето. Left=right=old е зададено, inc=1 е нарастването на търсенето.
4. Проверява се неравенството value>=array[old]. Когато се изпълни, отидете на следващия параграф (5), в противен случай отидете на параграф (7).
5. Дясната граница на търсенето се прибира още повече: дясно=дясно+вкл. Ако right>=n-1, тогава задайте right=n-1 и отидете на двоично търсене.
6. Проверете value>=array[right]. Ако това неравенство е вярно, тогава лявата граница се премества на мястото на дясната: left=right, inc се умножава по 2 и се връщаме към (5). В противен случай преминаваме към двоично търсене.
7. Лявата рамка е прибрана: ляво=ляво-вкл. Ако остане⇐0, тогавазадайте left=0 и отидете на двоично търсене.
8. Проверка на стойността
9. Двоичното търсене се извършва в масива с ограничени индекси отляво и отдясно. В този случай всеки път интервалът се намалява около 2 пъти (въз основа на паритета на разликата), докато разликата между ляво и дясно достигне 1. След това връщаме ляво като резултат, като едновременно присвояваме old=left.
Следното е C програма, която прилага алгоритъм за търсене в подреден масив от реални числа.
Забележка: за успешната работа на алгоритъма е препоръчително да зададете *old=-1 или друго число при първоначалното стартиране, което гарантира двоично търсене при първото преминаване.
Двоично търсене в масив
На практика доста често се извършва търсене в масив, чиито елементи са подредени по някакъв критерий (такива масиви се наричат подредени). Например, масив от фамилни имена, като правило, се сортира по азбучен ред, масив от данни за времето се подрежда по дати на наблюдение. Ако масивът е подреден, тогава се използват други алгоритми, които са по-ефективни от простия метод на изброяване, един от които е методът на двоично търсене. Нека има масив от цели числа, сортирани във възходящ ред. Необходимо е да се определи дали този масив съдържа някакво число (извадка). Методът (алгоритъмът) за двоично търсене се реализира по следния начин:
1. Първо се сравнява извадката със средния (по номер) елемент на масива.Ако извадката е равна на средния елемент, проблемът е решен. Ако извадката е по-голяма от средния елемент, това означава, че търсеният елемент се намира под средния елемент (между елементите с номера sred + 1 и niz), а sred + i се приема като нова стойност на глагола, а стойността на niz не се променя. Ако извадката е по-малка от средния елемент, това означава, че търсеният елемент се намира над среднияелемент (между елементите с номера verh и sred-1), като sred-1 се приема като новата стойност на niz, а стойността на verh не се променя
2. След като се определи частта от масива, която може да съдържа необходимия елемент, новата стойност на sred се изчислява по формулата (niz-verh) /2+verh и търсенето продължава.
Писане на програма, която извършва двоично търсене на елемент в сортиран масив
Разработка на алгоритъм
Двоичното търсене трябва да се извърши в предварително сортиран масив. Намира се средният елемент на масива и се сравнява с желаната стойност. Ако те са равни, тогава търсенето е завършено, ако желаната стойност е по-малка от стойността на средния елемент, тогава по-нататъшното търсене се извършва в лявата половина на масива, в противен случай - в дясната. Алгоритъм за търсене:
1. Определете средния елемент на масива
2. Ако стойността му е равна на желаната, то елементът е намерен. Отидете на стъпка 6
3. Ако броят на елементите на масива е 1, значи елементът не е намерен. Отидете на стъпка 6
4. Ако желаната стойност е по-малка от стойността на средния елемент, тогава вземете като масив всички елементи отляво на средния елемент и отидете на стъпка 1
5. вземете като масив всички елементи вдясно от средата и отидете на стъпка 1
Описание на метода на решение
Търсенето на желаната стойност сред елементите на сортиран масив започва с определяне на стойността на централния елемент на този масив. Сравнява се с желаната стойност и в зависимост от резултатите от сравнението се предприемат определени действия. Ако желаните и централните стойности са равни, тогава търсенето е завършено успешно. Ако желаната стойност е по-малка или по-голяма от централната стойност, тогава се формира масив, състоящ се от елементи, разположени съответно отляво или отдясно на централната. След това потърсетеитерира върху новия масив. В програмата алгоритъмът е реализиран чрез рекурсия.
Първоначалният масив се създава чрез зареждане на елементите му от текстов файл. Числата във файла трябва да бъдат разделени с интервали.
Блокова схема на алгоритъма
Примерна програма
Въведете името на файла с масив от числа: test.txt
23 45 10 -4 8 1 0 8 39
Заредени са 9 елемента от масива.
Зарежда се следният масив A[9]:
[ 23 45 10 -4 8 1 0 8 39 ]
Нека сортираме масива:
[ -4 0 1 8 8 10 23 39 45 ]
Намерете елемент от масива v=10
Нека започнем двоично търсене.
Итерация #1, масив за търсене: [ -4 0 1 8 8 10 23 39 45 ]
Итерация #2, масив за търсене: [ 10 23 39 45 ]