If you're seeing this message, it means we're having trouble loading external resources on our website.

Ако си зад уеб филтър, моля, увери се, че домейните *. kastatic.org и *. kasandbox.org са разрешени.

Основно съдържание

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

Да помислим за двоичното търсене върху сортиран масив. Да, JavaScript вече осигурява методи за определяне дали даден елемент е в масива и, ако е, да определи неговата позиция (както е в много езици за програмиране), но ние искаме да имплементираме това сами, за да разбереш как можеш да имплементираш подобни методи. Ето един JavaScript масив с първите 25 прости числа, подредени във възходящ ред:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Да предположим, че искаме да проверим дали числото 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:
  1. Нека min = 0 и max = n-1.
  2. Изчисляваме guess като средно аритметично на max и min, закръглено надолу (за да получим цяло число).
  3. Ако array[guess] е равно на target, тогава спираме. Намерихме го! Връщаме guess.
  4. Ако предположеното число е прекалено малко, или array[guess] < target, тогава задаваме min = guess + 1.
  5. В противен случай, предположеното число е прекалено голямо. Задаваме max = guess - 1.
  6. Връщаме се на стъпка 2.

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

Ще редуваме български, псевдокод и 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, знаем, че търсеното число не се съдържа в сортирания масив. Това е модифицираният псевдокод за двоично търсене в случая, когато търсеното число не бъде намерено:
  1. Нека min = 0 и max = n-1.
  2. Ако max < min, тогава спираме: target не се съдържа в array. Връщаме -1.
  3. Изчисляваме guess като средно артиметично на max и min, закръглено надолу (за да е цяло число).
  4. Ако array[guess] е равно на target, тогава спираме. Намерихме числото! Връщаме guess.
  5. Ако предположението е прекалено малко, т.е. array[guess] < target, тогава задаваме на min = guess + 1.
  6. В противен случай предположението е прекалено голямо. Задаваме на max = guess - 1.
  7. Връщаме се на стъпка 2.
След като заедно разгледахме псевдокода, ще опиташ самостоятелно да имплементираш двоичното търсене. Можеш да гледаш псевдокода – всъщност това е препоръчително, защото така ще разбереш по-добре какво означава да превърнеш псевдокода в програма.
Това съдържание е резултат от съвместната дейност на преподавателите по Компютърни науки в Дартмут Thomas Cormen и Devin Balkcom, както и на екипа по компютърни науки на Кан Академия. Съдържанието е лицензирано CC-BY-NC-SA.

Искаш ли да се присъединиш към разговора?

Все още няма публикации.
Разбираш ли английски? Натисни тук, за да видиш още дискусии в английския сайт на Кан Академия.