Имплементиране на двоично търсене в масив

Да помислим за двоичното търсене върху сортиран масив. Да, JavaScript вече осигурява методи за определяне дали даден елемент е в масива и, ако е, да определи неговата позиция (както е в много езици за програмиране), но ние искаме да имплементираме това сами, за да разбереш как можеш да имплементираш подобни методи. Ето един JavaScript масив с първите 25 прости числа, подредени във възходящ ред:

Да предположим, че искаме да проверим дали числото 67 е просто. Ако 67 е в масива, значи то е просто.

Освен това може да искаме да разберем колко други прости числа са по-малки от 67. Ако намерим позицията на числото 67 в масива, то ние ще можем да разберем и колко по-малки от него прости числа има.

Позицията на елемент в масива се нарича негов индекс. Индексите в масив започват от 0 и продължават нагоре. Ако някой елемент е с индекс 0, то той е първият елемент на дадения масив. Ако има индекс 3, то значи има 3 елемента, които са преди него в масива.

Поглеждайки примера по-долу, можем да прочетем масива от прости числа от ляво надясно, по едно число на ход, докато не стигнем до числото 67 (в розовата кутийка) и видим, че то е с индекс 18 в масива. Преглеждането на числата в този ред се нарича линейно търсене.

Щом вече веднъж знаем че простото число 67 е на позиция 18, ние можем да го идентифицираме като просто. Освен това можем бързо да видим, че има 18 елемента преди него в масива, което означава, че има 18 по-малки от него прости числа.

Видя ли колко стъпки включваше това? Двоичното търсене може да е по-ефективно. Понеже масивът primes съдържа 25 числа, индексите им ще бъдат в диапазона от 0 до 24. Използваме псевдокода от преди и започваме, като задаваме min = 0 и max = 24. Следователно първото предположение в двоичното търсене ще бъде на индекс 12 (което е (0 + 24) / 2). Дали primes[12] е равно на 67? Не, primes[12] е 41.

Дали индексът, който търсим, е по-голям или по-малък от 12? Тъй като стойностите в масива са във възходящ ред, а 41 < 67, стойността 67 трябва да бъде отдясно на индекс 12. С други думи, индексът, който се опитваме да намерим, е по-голям от 12. Актуализираме стойността на min на 12 + 1, или 13, и оставяме max непроменено на 24.

Кой е следващият индекс, който търсим? Средното аритметично на 13 и 24 е 18,5, което закръгляме надолу до 18, тъй като индексът в масива трябва да е цяло число. Намираме, че primes[18] е 67.

Алгоритъмът за двоично търсене спира в този момент, тъй като вече е намерил отговора. Отне ни само 2 предположения вместо 19, които ни трябваха с линейното търсене. Можеш отново да минеш през стъпките с визуализацията по-долу:

Току-що описахме алгоритъма за двоично търсене на български, разглеждайки един пример. Това е един от начините да го направим, но обяснението на човешки език може да варира в качеството си. То може да бъде твърде късо или твърде дълго и – най-важното – не винаги е достатъчно прецизно. Можем да прескочим до пример за двоично търсене на програмен език като JavaScript или Python, но програмите съдържат твърде много детайли, поради изисквания, наложени от самите програмни езици и защото програмите трябва да се справят с грешки, породени от лоши данни, потребителски грешки или системни грешки – а това може да направи алгоритъма труден за разбиране. Ето защо предпочитаме да описваме алгоритмите с нещо, наречено псевдокод, което смесва човешкия език с елементи от езиците за програмиране.

Това е псевдокодът за двоично търсене, модифициран за търсене в масив. Входните данни са масивът array; броят n на елементите в масива array; и target, числото, което търсим. Изходът е индексът на target в array:

Ще редуваме български, псевдокод и JavaScript в тези уроци в зависимост от ситуацията. Като програмист трябва да се научиш да разбираш псевдокод и да можеш да го превръщаш в език по избор – така че дори и да използваш JavaScript тук, за теб трябва да е лесно да имплементираш псевдокод с други езици.

Как ще превърнем псевдокода от примера по-горе в програма на JavaScript? Трябва да създадем функция, защото пишем код, който приема вход и връща изход, и искаме кодът да бъде използван многократно за различни входове. Параметрите на функцията – нека я наречем binarySearch – ще бъдат масив и целева стойност, а върнатата стойност на функцията ще бъде индексът на мястото, където е намерена целевата стойност.

Сега да се фокусираме върху тялото на функцията и да решим как да осъществим нашия план. Стъпка 6 казва да се върнем към стъпка 2. Това звучи като цикъл. Какъв трябва да бъде – for-цикъл или while-цикъл? Ако наистина искаш да използваш for-цикъл, можеш да го направиш, но индексите, предположени в двоичното търсене, не са в последователния ред, който се използва във for-цикъла. Може да предположим първо индекс 12, а след това 18, според някакви изчисления. Ето защо while-цикъл е по-добрият избор.

Освен това има и една важна стъпка, която липсва в псевдокода, която е без значение за играта за познаване, но е от значение за двоичното търсене в масив. Какво ще стане, ако числото, което търсим, не е в масива? Да започнем като разберем какъв индекс трябва да върне функцията binarySearch в този случай. Трябва да е число, което не може да бъде валиден индекс в масива. Ще използваме -1, тъй като не може да е валиден индекс в масива. (Всъщност всяко отрицателно число би свършило работа.)

Търсеното число не се съдържа в масива, ако не са останали възможни предположения. Да предположим, че в нашия пример търсим числото 10 в масива primes. Ако се съдържа в него, 10 ще бъде между стойностите 7 и 11, които са на индекси 3 и 4. Ако вземеш индексите на стойностите на min и max, каквото е изпълнението на функциятаbinarySearch, ще разбереш, че min е равно на 3, а max е равно на 4. Тогава предположението е на индекс 3 (тъй като (3 + 4) / 2 е равно на 3,5, а ние закръгляме надолу), а primes[3] е по-малко от 10, тогава min става 4. Тъй като и min, и max са равни на 4, предположението трябва да е индекс 4, а primes[4] е по-голямо от 10. Сега max става 3. Какво означава това, че min е равно на 4, а max е равно на 3? Това означава, че единствените възможни предположения са поне 4 и най-много 3. Няма такива числа! В този момент можем да направим заключението, че търсеното число 10 не се съдържа в масива primes, а функцията binarySearch ще върне -1. Като цяло, когато max стане строго по-малко от min, знаем, че търсеното число не се съдържа в сортирания масив. Това е модифицираният псевдокод за двоично търсене в случая, когато търсеното число не бъде намерено:

След като заедно разгледахме псевдокода, ще опиташ самостоятелно да имплементираш двоичното търсене. Можеш да гледаш псевдокода – всъщност това е препоръчително, защото така ще разбереш по-добре какво означава да превърнеш псевдокода в програма.

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