Двоично търсене

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

Един от най-често срещаните начини за използване на двоично търсене е намиране на елемент в масив. Например в звездния каталог Tycho-2 се съдържа информация за 2 539 913-те най-ярки звезди в нашата галактика. Да предположим, че искаш да потърсиш в каталога определена звезда по нейното име. Ако програмата премине през всяка звезда от каталога, като започне от първата, (което е алгоритъм, наречен линейно търсене), в най-лошия случай компютърът трябва да прегледа всичките 2 539 913 звезди, за да намери звездата, която търсиш. Ако имената на звездите в каталога са сортирани по азбучен ред, двоичното търсене няма да прегледа повече от 22 звезди дори и в най-лошия случай.

Следващите няколко страници обясняват как да опишем алгоритъма внимателно, как да го имплементираме в JavaScript и как да анализираме ефективността му.

Когато даваме на друг човек описание на един алгоритъм, обикновено дори и непълно описание е достатъчно. Някои детайли могат да бъдат пропуснати. Ако правиш торта по рецепта, в рецептата не се казва как да отвориш хладилника, за да извадиш яйцата, или как да счупиш яйцата. Хората знаят интуитивно как да попълнят липсващите детайли, но компютърните програми – не. Ето защо в компютърните програми трябва да опишем алгоритъма напълно.

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

Нека внимателно разгледаме как можем да опишем двоичното търсене. Главната идея на двоичното търсене е да следи моментния обхват на някакви разумни предположения. Да кажем, че си намисля число между 1 и 100, както в тази игра. Ако предположиш 25 и ти кажа, че моето число е по-голямо, и после предположиш 81, а аз ти кажа, че моето число е по-малко, то числата между 26 и 80 са разумните предположения. Тук червената област от числовата ос съдържа разумните предположения, а черната област показва предположенията, които изключваме:

При всеки ход избираш предположение, което разделя областта на разумните предположения на два обхвата със сравнително близки размери. Ако предположението не е правилно, казвам, че числото е прекалено голямо или прекалено малко, а ти можеш да изключиш около половината от разумните предположения. Например, ако в момента обхватът на разумните предположения е 26 до 80, можеш да предположиш някакво средно число, $(26+80)/2$‍, или 53. Ако ти кажа, че 53 е прекално голямо, можеш да изключиш всички числа от 53 до 80, което ти оставя 26 до 52 като нов обхват на разумните предположения, който има наполовина по-малък размер.

В нашата игра можем да следим областта на разумните предположения, като използваме няколко променливи. Нека променливата $min$‍ да бъде текущото най-малко предположение за първия ход, а променливата $max$‍ да бъде текущото най-голямо предположение. Входът на задачата е числото $n$‍, най-голямото възможно число, което опонентът може да си намисли. Приемаме, че най-малкото възможно число е 1, но можем лесно да променим задачата така, че да приема най-малкото възможно число като втори вход.

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

Бихме могли да направим това описание дори по-прецизно, като ясно опишем входните и изходните данни за алгоритъма и като изясним какво имаме предвид с инструкции като "познай число" и "спри". Но засега това са достатъчно подробности.

Нататък ще видим как можем да използваме двоично търсене в масив и ще обсъдим как да превърнем описанията на алгоритми в истински работещ код.

Това съдържание е резултат от съвместната дейност на преподавателите Томас Кормен и Девин Балком от Компютърни науки Дартмут, както и компютърния екип на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.