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

Как работи?

Както можете да видите на диаграмата, на всяка стъпка от алгоритъма се прави сравнение и процедурата се разклонява в една от двете посоки. По-конкретно, стойността на ключа се сравнява със средния елемент на масива. Ако ключовата стойност е по-малка или по-голяма от този среден елемент, алгоритъмът знае коя половина от масива да продължи да търси, защото масивът е сортиран. Този процес се повтаря върху прогресивно по-малки сегменти от масива, докато се намери стойността.

Тъй като всяка стъпка в алгоритъма разделя размера на масива наполовина, двоичното търсене ще завърши успешно в логаритмично време. Това означава, че най-лошият сценарий за масив от n елемента е гарантиран в log (n) операции.

Двоични, Условия за програмиране, Търсене