Методът двоично търсене се нарича Binary Search на английски. В литературата и в университета също така може да се срещне като Bisection Method (метод на бисекцията) или Dichotomy (Дихотомия).

В информатиката, двоично търсене е алгоритъм, който се използва за намиране на позицията на елемент или стойност в подредена структура от данни, например в предварително сортиран масив.Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990).Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.Weisstein, Eric W., „Binary Search“, MathWorld. За разлика от последователното търсене, при двоичното търсене са необходими много по-малко стъпки за намиране на търсения елемент. При двоичното търсене, размерът на претърсваното пространство намалява на половина след всяка стъпка. Съществува също така модификация на техниката, при която той намалява само с една трета, но решава по-сложен проблем. Тази техника се нарича троично търсене.

Когато искаме многократно да търсим различни елементи в даден масив, е по-добре първо да го сортираме и после да използваме метода на двоичното търсене. Това е бърз метод за претърсване на вече сортиран масив.Светлин Наков и колектив, Програмиране за .NET Framework – том 1 Двоичното търсене се основава на разделянето на дадено множество от записи на две равни части, сравняване на търсения идентификатор с последния запис от долната половина или с първия запис от горната половина и установяване по този начин в коя половина се намира той. Следва търсене в така откритата половина чрез нейното разделяне на две части и така нататък докато се стигне до желания запис. По този начин се намалява броят на четенията на записи и се спестява време от тази най-времеемка компютърна операция. Според теория на вероятностите при брой на записите n и последователно търсене средновероятният брой на четенията и свързаните с тях сравнения е n/2. При двоично търсене този брой е значително по-малък. Тъй като, само по себе си, двоичното търсене е сравнително кратко и просто за писане, най-често в задачи то бива съчетано с друг, по-сложен алгоритъм или структура данни. Много често се срещат не малък брой задачи, които се решават (поне частично) с двоично търсене. Този метод е много важен и по друга причина – той е един от популярните въпроси на интервюта за работа. Редица софтуерни компании считат, че ако кандидатът за работно място не може да напише двоично търсене, то няма никакъв смисъл да го наемат като програмист.

Максималният брой стъпки, необходими на алгоритъма за намирането на елемент в сортиран масив, е двоичен логаритъм от дължината на масива. Тоест, за намиране на елемент в сортиран масив от 1 милион елемента алгоритъмът ще извърши най-много 20 стъпки. На всяка стъпка алгоритъмът сравнява търсената стойност със стойността на средния елемент от масива. В случай че средният елемент съвпада с търсения елемент, тогава алгоритъмът завършва – елементът е намерен и неговият индекс (позиция) се връща.Binary search algorithm

Общ преглед Търсене в сортиран масив е стандартна задача. Речникът, например, е сортиран списък от дефиниции на думи. Търсене на конкретна дума ще намери определението за нея. Телефонен указател е сортиран списък от имена, адреси и телефонни номера. По името на даден човек може да се намери неговият адрес и номер.

Ако списъкът, по който да се зададе търсенето, съдържа повече от няколко артикула (например дузина), двоичното търсене ще отнеме много по-малко сравнения от линейното търсене, но списъкът трябва да бъде сортиран.

Стандартният подход при решаването на сходни проблеми е да се почне от началото – 1, 2, 3 [...], и да се сравнява всяко едно от числата с търсената стойност. Но ако числата са 100 000, търсенето ще продължи твърде дълго. Същото важи и ако се започне от края на масива, 100 000, 999 999, 999 998 […], защото търсенето число може да е 1. При двоичното търсене размерът на претърсвания интервал намалява на половина при всяка стъпка, и така времето за решаване на задачата се съкращава драстично.

Двоично търсене на елемент, равен на зададена стойност При многократно търсене на различни елементи в даден масив е по-добре първо да го сортираме и след това да използваме двоично търсене. Сложността, с която се претърсва масив от n елемента, е Θ(log(n)).

Започва се с целия масив. Сравнява се търсената стойност с елемента, който е по средата на масива. Възможни са следните три случая: стойностите са равни – търсеният елемент е намерен; търсената стойност е по-малка – търсенето продължава в левия подмасив; търсената стойност е по-голяма – търсенето продължава в десния подмасив.

След това по същия начин се търси в подмасива, после в негов подмасив и т.н. Процесът продължава до намиране на търсения елемент или до подмасив от нито един елемент (масивът не съдържа търсената стойност).

Примери

Пример 1 Ако в дадена поредица имаме седем числа (9, 7, 6, 4, 3, 2, 1) и търсим числото 6, на първата стъпка средният елемент ще е 4. Тъй

като 4 не съвпада с търсената от нас стойност, алгоритъмът продължава да търси в лявата половина, т.е. 9, 7, и 6. На следващата стъпка отново се определя средният елемент, който е числото 7. Той е по-голям от търсената стойност. Всички числа вляво се елиминират и остава елементът 6. Тъй като той съвпада с търсената от нас стойност, алгоритъмът приключва.

Алгоритъм, основаващ се на тази идея, е реализиран като функция от логически тип, която връща стойност True или False, в зависимост от това дали в масива е намерен или не е намерен елемент, равен на зададения.itplamen.wordpress.com

Пример 2 Още един, подобен на по-горе изложения пример. Масивът, в който ще се търси, е: list = [1, 4, 10, 12, 15, 20, 22]. Стойността, която трябва да намерим е: num = 10.

Търсенето започва на num като първо се сравнява с числото, намиращо се в средата на масива – 12. 10 е по-малкото от 12. Търсенето започва с числата, намиращи в лявата от 12 част от масива: 1, 4, 10.

Първо се сравнява 10 с 1. Търсеното число не е намерено.

Преминава се към следващото число от масива – 4. Числото е по-голямо от числото от масива. Преминава се към следващата стойност.

Сравнява се числото num със следващото число – 10. Числото num e равно на числото от масива. Така се намира num.

Игра познай номера Тази игра, започва с нещо като: „Мисля си едно целочислено число между 40 и 60 включително, а ти трябва да го познаеш. Аз ще казвам „нагоре“, „надолу“ или „да!“.“

Да предположим, че N е числото от възможни стойности (в нашия пример 21 възможни примера), и тогава (log2 N) въпроси са нужни, за да се определи числото, тъй като всеки въпрос разделя търсеното място. Обърнете внимание, че един въпрос (повтаряне/итерация) по-малко е нужен отколкото за обикновения алгоритъм, защото номерът вече се намира в определени рамки.

Дори ако числото, което трябва да познаем, е произволно (без да имаме горна граница за N), то може да бъде намерено чрез 2(log2 N) + 1 стъпки (N е търсеното число), намирайки първо горната граница с едностранно търсене (или експоненциално търсене – търсене в масив, започвайки от определена начална точка, при което търсеният елемент или се очаква да се намира близо до началната точка или горната (долната) граница са неизвестни).Binary search algorithm, Number guessing game Например, ако търсеното число е 11, следната последователност може да бъде използвана, за да бъде то намерено: 1 (нагоре), 2 (нагоре), 4 (нагоре), 8 (надолу), 16 (надолу), 12 (надолу), 10 (нагоре). Сега знаем, че числото трябва да е 11, защото е по-голямо от 10 и по-малко от 12.

Можем също да разширим метода на търсене, добавяйки отрицателна стойност. Например, за да намерим -13, може да ползваме следното търсене: 0, −1, −2, −4, −8, −16, −12, −14.

Следващия пример, който ще разгледаме е: да предположим, че имаме сортиран масив [1,2,3,4,5,6,7] и искаме да намерим числото 6, намиращо се на 5 позиция в масива.

Първо трябва да намерим стойността на log N, която ще ни бъде полезна при сравняването на елементите и при избиране на правилната част от масива, в която ще бъде търсено. Можем да използваме while цикъл:

int getLogOf(int N) { int log2 = 0 while((1 << log2) <= N)log2++; return --log2; } След това можем да започнем търсенето:

int find(int array[], int N, int K) { int log2 = getLogOf(N); int currentPosition = 0; while(log2 >= 0)

// check if we got a solution // if yes, the return it if(array[curPosition] == K) return curPosition; // check the next postion int newPosition = curPosition + (1 << log2); // if it's smaller or equal then we have to // update the current position if(newPosition < N && array[newPosition] <= K) curPosition = newPosition; // decrement the skip size log2--;

return -1; }Имаме масив [1,2,3,4,5,6,7] и търсим числото 6. Тъй като дължината на масива е 7, то стойността на log 2 от 7 е 2 (2^2 = 4, 2^3 = 8 – взимаме по-малката стойност). Нека да видим как преминава търсенето:Iter1: [1,2,3,4,5,6,7] log=2, currentPosition = 0, newPosition = 0 + 2 ^ 2 = 4, array[newPosition] = 5 < 6 currentPosition = newPosition log--Iter2: [1,2,3,4,5,6,7]log=1, currentPosition = 4, newPosition = 4 + 2 ^ 1 = 6, array[newPosition] = 7 > 6log--Iter3: [1,2,3,4,5,6,7]log=0, currentPosition = 4, newPosition= 4 + 2 ^ 0 = 5, array[newPosition] = 6 == 6return 5Така намираме търсеното число.

Имплементиране Имплементацията е проста и сравнително стандартна, вследствие на което много често се ползва един и същ шаблон винаги, когато се пише „байнъри“.

Първо, тъй като се търси нещо в някакъв интервал, е хубаво да си представим интервала по някакъв начин. Често се търси нещо в масив, като интервалът ще бъде представен чрез най-левия и най-десния валиден индекс. Понякога, обаче ще имаме друга функция, в която се търси отговора.  За сега ще се разгледат само дискретни функции (тоест такива, които имат краен брой елементи), като например интервал от цели числа или индекс в масив.

Интервала може да се представи чрез две числа – най-лявата (малката) възможна стойност на интервала и най-дясната (голямата) такава, които се наричат left и right или за по-кратко l и r. На всяка стъпка ще се изчислява една нова стойност – средата на интервала – в променлива mid или m. За да се намери средата на интервал по принцип се взима левия му край и се прибавя половината. Това, като код е:

mid = left + (right – left) / 2

По-често, обаче, се ползва малко по-кратък метод на записване на същото нещо: mid = (left + right) / 2 Трябва да се внимава за „overflow“ ако се използва съкратения вариант! Дори целият интервал да се събира в даден тип, то сумата на лявата и дясната граница може да не се събира. Например, какво става ако има интервала [1, 2000000000], границите са от тип int (съвсем логично, тъй като типът поддържа този интервал) и се използва int mid = (left + right) / 2;? Ако отговорът е близък до горната граница, ще има стъпки, в които (left + right) ще прехвърли възможностите на int и програмата ще даде грешен резултат. В това отношение по-дългият запис е по-безопасен, тъй като няма този проблем. Докога се върти цикъла? Това частично зависи от задачата, но най-често при дискретния вариант – докато интервалът съдържа поне един елемент. Това лесно се изразява чрез while цикъл – например най-често се среща while(left <= right) или while(left < right), в зависимост от предпочитанията. 

Примерна имплементация с цикъл C# int binarySearch(int[] array, int value, int left, int right) { while (left <= right)

int middle = (left + right) / 2; if (array[middle] == value)

return middle;

else if (array[middle] > value)

right = middle - 1;

else

left = middle + 1;

return -1; }

Visual Basic Function BinarySearch(ByVal A() As Integer, ByVal value As Integer) As Integer Dim low As Integer = 0 Dim high As Integer = A.Length – 1 Dim middle As Integer = 0

While low <= high middle = (low + high) / 2 If A(middle) > value Then high = middle – 1 ElseIf A(middle) < value Then low = middle + 1 Else Return middle End If