Пребарување е една од основните операции кои се среќаваат при решавањето на разни проблеми. Во ова предавање, ќе разгледаме еден од основните и најкористените алгоритми од оваа област – т.н. бинарно пребарување. Иако алгоритамот сам по себе е доста едноставен, тој наоѓа примена во многу подрачја, и се користи во разни компјутерски програми и системи.

Наједноставниот начин да го сфатиме алгоритамот е да го замислиме следниот проблем: погодување на замислен број. Имено, нека некое лице одбере произволен број од 1 до 100, и нека треба ние да го погодиме бројот кој е замислен. Притоа, при секој наш обид, добиваме одговор дали бројот кој што сме го кажале е помал од замислениот, поголем, или пак доколку веќе сме го погодиле точниот број.

Како можеме да го решиме овој проблем? Нормално, кажувајќи ги сите броеви почнувајќи од 1, 2, 3, ..., па се додека не погодиме, е едно можно решение - но, секако, не е најдоброто кое што можеме да го постигнеме. Дали постои начин да ја искористиме повратната информација што ја добиваме во однос на тоа дали нашиот кажан број е помал или поголем од замислениот? Се разбира дека можеме - со т.н. алгоритам за бинарно пребарување. Притоа, како што ќе видиме од повеќе примери во ова предавање, самата постапка е исклучително едноставна – при секој чекор, го разгледуваме средниот број од интервалот (на пример, ако разгледуваме броеви од 1 до 100, средниот број е 50). Доколку тој број е поголем од замислениот, го спроведуваме истиот алгоритам на левата половина од преостанатиот интервал (1 - 49); а, ако е помал од замислениот, на десната половина од преостанатиот интервал (51 – 100). Така продолжуваме се додека не го погодиме точниот број. Притоа, овој алгоритам има логаритамска сложеност O(logN), и е исклучително едноставен. На пример, доколку со истиот се обидуваме да најдеме број во телефонски именик од сите луѓе на планетата (каде имињата се подредени, па можеме, на сличен начин, да го делиме интервалот на половина), ќе ни биде потребно да направиме само околу 30 проверки. Тука, ја гледаме моќта на бинарното пребарување.

Сега, да разгледаме уште поконкретен пример. Нека имаме подредена низа од цели или реални броеви. Користејќи ја истата идеја која што ја видовме погоре, можеме со логаритамска сложеност O(logN) да пронајдеме дали еден елемент постои во низата. Притоа, алгоритамот е исклучително едноставен за реализација. Забележете дека, во кодот даден во продолжение, со left и right ги означуваме границите на интервалот кој го разгледуваме – на почеток, тој ја опфаќа целата низа, а како што споредуваме елементи, го делиме истиот (во секој чекор) на половина. Ова е идејата која овозможува бинарното пребарување да функционира толку ефикасно.

int bsearch(vector<int> &arr, int K)
{
     int left = 0, right = arr.size() - 1;
     
     while (left <= right)
     {
          int middle = (left + right) / 2;
          
          if(arr[middle] == K)
          {
               //vrati go tochniot indeks
               return middle;
          }
          
          if(arr[middle] > K)
          {
               //prodolzhi so levata polovina na intervalot
               right = middle - 1;
          }
          else
          {
               //prodolzhi so desnata polovina na intervalot
               left = middle + 1;
          }
     }
     
     //ne postoi, vo sprotivno
     //(return middle) kje se povikashe pogore
     //i funkcijata nema da stigneshe do tuka
     return -1;
}

Се разбира, за барање дали еден елемент постои како податок, можеме да користиме и податочни структури. Најпознатите од нив кои се користат за решавање на овој проблем, бинарните дрва и хеш табелите, веќе ги видовме во претходните предавања. Дали ќе користиме некоја од нив или бинарно пребарување, зависи од самиот проблем – дали податоците ни се дадени како низа (и можеби, однапред подредени), дали имаме можност да користиме додатна меморија за нови податочни структури, итн. Во повеќето проблеми, било кое решение од понудените е доволно ефикасно, и може да се користи без никакви потешкотии.

Сепак, како што ќе видиме во продолжение, постојат и неколку други проблеми кои може да се решат со бинарно пребарување.

Воопштување на проблемот

Во претходниот пример, разгледавме ситуација каде што баравме дали еден елемент постои во низа или не. Слично, во проблемот со замислениот број, се обидувавме да пронајдеме точно еден број, кој беше однапред замислен. Но, како што ќе видиме во продолжение, алгоритамот за бинарно пребарување може да се искористи и во други ситуации. Имено, да замислиме ситуација каде што, повторно, имаме низа каде што елементите се подредени, и барање да го најдеме најмалиот број кој е поголем или еднаков на одреден број K. На пример, нека ја имаме низата [1, 2, 5, 9, 13, 20] и барање да го најдеме најмалиот број од низата поголем или еднаков на K=10. Во оваа ситуација, бројот кој што го бараме е 13, бидејќи е тоа првиот број во низата кој што е поголем или еднаков на K=10.

Како што можете да погодите, и овој проблем можеме да го решиме со бинарно пребарување. И повторно, како и во претходниот случај, зборуваме за алгоритам со логаритамска сложеност O(logN). Дополнително, како и при пребарувањето на елемент во низа, кодот за реализација на решението е исклучително едноставен и краток за пишување. Сепак, истиот ќе изгледа малку поинаку - имено, сега не сме во можност да го елиминираме елементот кој го разгледуваме како претходно (каде користевме left=middle+1 и right=middle-1), туку елементот кој го разгледуваме во моментот можеби и е вредноста која на крај ќе излезе како онаа што ја бараме. Поради тоа, иако генерално идејата е иста, и повторно имаме ситуација каде што интервалот ќе го делиме на половина, ќе треба да направиме неколку ситни промени во реализацијата на истиот.

int bsearch(vector<int> &arr, int K)
{
     
     if(arr[0] >= K)
     {
          //vekje prviot (najmaliot) broj e dovolno golem
          return arr[0];
     }
     
     if(arr[arr.size() - 1] < K)
     {
          //nitu posledniot (najgolemiot) broj ne e dovolno golem
          return -1;
     }
     
     int left = 0, right = arr.size() - 1;
     while (left + 1 < right)
     {
          int middle = (left + right) / 2;
          
          if(arr[middle] < K)
          {
               //baraj pogolemi broevi
               left = middle;
          }
          else
          {
               //baraj pomali broevi
               right = middle;
          }
     }
     
     return arr[right];
}

Промените кои ги направивме се однесуваат на следното: додавање на два услови на почетокот на функцијата за проверка на првата и последната вредност, менување на условот во циклусот (сега имаме left + 1 < right), како и чување на разгледаните вредности наместо нивно отфрлање (left=middle наместо left=middle+1, и right=middle наместо right=middle-1). Притоа, забележете дека, во функцијата, left секогаш покажува на невалидна вредност (број кој не е поголем или еднаков на K), додека right секогаш покажува на валидна вредност (број кој е поголем или еднаков на K). Со циклусот, ова го повторуваме се додека тие два броја се разликуваат за повеќе од 1. Кога истите ќе се разликуваат за најмногу 1, знаеме дека right покажува на точната позиција (онаа која што ја бараме).

Сега, сигурно се прашувате зошто го направивме сето ова? Зошто не можевме да го искористиме истиот код како при пребарувањето на вредност во низа, и зошто мора посебно да ги разгледаме условите за двата краја, но и да го промениме условот во циклусот? Одговорот е едноставен – бидејќи сега не можеме да ја елиминираме средната вредност (middle) оти не знаеме што има во остатокот од интервалот. Од друга страна, доколку го оставевме условот во циклусот како претходно (наместо left+1 < right), и не ги разгледавме првичните услови, можевме да дојдеме во ситуација каде што ќе бевме закочени во бесконечен циклус. Имено, кога left и right се разликуваат за 1, middle е еднакво на left (бидејќи користиме делење на цели броеви па, на пример, left=3, right=4, и (3+4)/2 = 3, па го разгледуваме тој број). Поради тоа, во таква ситуација, можно беше да се случи првиот услов (arr[middle] < K) да е исполнет, па да поставиме вредност left = middle. Но, бидејќи, како што кажавме претходно, middle е веќе еднакво на left, немаше да настанат никакви промени, па повторно ќе се извршат истите операции на ист интервал, и ќе бевме заглавени во бесконечен циклус.

За да споменеме колку е корисен алгоритамот кој што го разгледавме, ќе ни треба многу простор. Имено, истиот може да се искористи за решавање на разни проблеми, а не само проблеми со низи. Дел од нив ќе разгледаме во продолжение. Во однос на проблеми со низи, се додека вредностите се подредени, можно е да се прават разни анализи. На пример, нека имаме низа каде што првите неколку елементи се нули, а останатите (во продолжение) не се. Во ваков случај, користејќи го алгоритамот за бинарно пребарување од претходно, можеме, на пример, да изброиме колку нули има во низата, со логаритамска сложеност O(logN). Единствено, за разлика од претходно, нема да враќаме вредности, туку позицијата (индексот) во низата каде што ќе најдеме број поголем од 0.

Слично, може да решиме и проблеми каде, барем директно, немаме низа. На пример, со алгоритамот за бинарно пребарување, можеме да пронајдеме каде има прекин во сигналот кај одреден километарски далновод/кабел – почетокот и крајот на истиот можеме да ги третираме како почетниот интервал, да провериме дали има сигнал кај станицата која се наоѓа на средината на истиот, и соодветно да ја разгледуваме едната или другата половина од интервалот. Значи, алгоритамот за бинарно пребарување може да се користи во многу ситуации – практично, секаде каде што имаме интервал од подредени вредности, или интервал каде што постои точка за која што важи дека сите делови пред таа точка не задоволуваат одреден услов, а сите делови по таа точка го задоволуваат условот. Точката, во овој случај, ја откриваме со бинарно пребарување.

Пред да продолжиме понатаму, важно е да напоменеме уште нешто. Имено, во кодот даден претходно, во низа баравме вредност која што е поголема или еднаква на K. Тука, всушност ја баравме најмалата вредност (најлевата во низата) за која е исполнет тој услов (>=K). Но, бинарното пребарување може да се искористи и за обратниот проблем – каде ја бараме најголемата вредност (најдесната во низата) за која е исполнет одреден услов – на пример, доколку во низата ја бараме најдесната вредност која што е помала или еднаква на K (наместо поголема). Во ваква ситуација, сите елементи до одредена позиција ќе го задоволуваат условот (<=K), па ние ја бараме последната (најдесната) од тие вредности.

Нормално, на истиот начин како и претходно, и ова се решава со бинарно пребарување. Како разлика во кодот, сега почетните услови ќе бидат малку поразлични (треба да провериме дали првиот елемент е можеби поголем, што би значело дека сите елементи се поголеми, односно дека не постои елемент кој е <=K), и дали можеби последниот е помал или еднаков (што значи дека тоа е елементот што го бараме – најдесниот за кој е исполнет условот). Дополнително, сега left ќе покажува на валидната вредност, а right на невалидната, па затоа на крајот ќе вратиме arr[left]. Како што гледате, со многу мали промени, бинарното пребарување го користиме за решавање на разни проблеми.

int bsearch(vector<int> &arr, int K)
{
     
     if(arr[0] > K)
     {
          return -1;
     }
     
     if(arr[arr.size() - 1] <= K)
     {
          return arr[arr.size() - 1];
     }
     
     int left = 0, right = arr.size() - 1;
     while (left + 1 < right)
     {
          int middle = (left + right) / 2;
          
          if(arr[middle] > K)
          {
               right = middle;
          }
          else
          {
               left = middle;
          }
     }
     
     return arr[left];
}

Реални броеви

На сличен начин како што користевме бинарно пребарување каде интервалот е ограничен со цели броеви, можеме да користиме и бинарно пребарување каде интервалот е ограничен со реални броеви. На пример, нека имаме задача каде што треба да ја одредиме осетливоста на која што треба да вклучиме одредени аларми, каде што позициите на истите ни се познати, а осетливоста (далечината на која што детектираат проблеми) нека ја претставиме со кружници. Целта, нека биде, да одредиме на која осетливост да ги вклучиме алармите, за истите да не се препокриваат (кружниците да не се сечат).

Тука, можеме да искористиме бинарно пребарување каде што ќе го бараме радиусот на кружниците - бидејќи постои вредност за радиусот каде што за помали вредности нема сечење на кружниците, а по таа вредност, сите поголеми радиуси ќе предизвикуваат допирање или препокривање на кружниците. На почеток, нека left=0 (најмалиот можен радиус), а right=10000000 (некоја голема вредност), и нека го делиме интервалот на половина се додека не дојдеме до бараниот податок - вредноста за радиусот каде веќе кружниците почнуваат да се сечат. Притоа, кога користиме бинарно пребарување кај реалните броеви, ќе имаме две мали разлики при реализацијата: имено, веќе нема да користиме целобројно делење, туку делење на реални броеви за пресметка на (left+right)/2.0; и, како втора разлика, циклусот ќе го извршиме конечен број пати (60-100), наместо да се мачиме да смислиме услов каде истиот да запре (како left+1<right, и слично). Причината за ова е едноставна – реалните броеви, кај компјутерите, не се чуваат со бесконечна прецизност, туку имаме само одреден број на битови (кај double, 64 бита) кои се користат за чување на податокот. 100 извршувања на циклусот при бинарно пребарување, ќе направи доволно стеснување на интервалот за да дојдеме до вредност која што е исклучително прецизна.

Кодот е доста поедноставен од претходно:

double bsearch(vector<pair<int, int> > &alarmPositions)
{
     
     double left = 0, right = 100000000;
     
     for(int i=0; i<100; i++)
     {
          double middle = (left + right) / 2.0;
          
          double radius = middle;
          if(circlesIntersect(alarmPositions, radius))
          {
               //baraj pomal radius
               right = middle;
          }
          else 
          {
               left = middle;
          }
     }
     
     return left; //ili "right", bidejki i dvete se mnogu blisku
}

Функцијата circlesIntersect() треба само да провери дали постојат две кружници кои се сечат меѓусебно (на пример, користејќи два for-циклуси, истата може да ги испроба сите парови на кружници). Како што видовме од повеќе примери, алгоритамот за бинарно пребарување е исклучително моќен и може да се користи за решавање на разни проблеми. Без разлика дали ќе бараме само една вредност, позиција каде што има некакви промени во низа, вредност каде што нешто се случува (сечење на кружници) и слично, алгоритамот е доволно моќен да ни помогне да дојдеме до саканиот податок исклучително ефикасно.

Интервали од броеви

Сега, да разгледаме и една интересна задача која може да се реши со помош на бинарно пребарување. Истата ќе ни овозможи да видиме како алгоритамот може да се искористи во ситуации каде што не е однапред јасно каква е поврзаноста на задачата со бинарното пребарување. (Имајте во предвид дека ова е многу сложена задача, од натпревар по информатика.)

Имено, нека ни се дадени неколку интервали од броеви, и нека треба да го најдеме бројот кој се наоѓа на X-тата позиција во низата од сите броеви од интервалите, ако истите се подредени од најмал до најголем. На пример, доколку ги имаме интервалите 3-10 и 5-9, низата ќе биде составена од сите елементи од првиот интервал (3, 4, 5, 6, 7, 8, 9, 10) и вториот интервал (5, 6, 7, 8, 9), значи ја имаме конечната низа: 3,4,5,5,6,6,7,7,8,8,9,9,10. Тука, бројот на X=1 позиција е 3, бројот на X=3 позиција е 5, итн.

Се разбира, веќе знаеме еден начин како ова можеме да го решиме. Ќе направиме една низа со динамичка големина, и ќе ги ставиме сите броеви од сите интервали. Вредностите во истата ќе ги подредиме (од најмала до најголема), и потоа само ќе го вратиме X-тиот елемент од низата. Сепак, овој алгоритам нема да функционира ефикасно доколку интервалите се големи – на пример, составени од милиони елементи. Во ваков случај, ќе чуваме и подредуваме низа која ќе ги содржи сите нив.

Овој проблем можеме да го решиме и со бинарно пребарување - без потреба за создавање на дополнителна низа, или користење на алгоритам за подредување на вредности. Едноставно, ќе разгледуваме секвенца составена од сите можни броеви (почнувајќи од најмалиот, на пример 3; па до најголемиот, на пример 10), и кога ќе разгледуваме одредена вредност (на пример, 6) ќе провериме колку вредности во интервалите се помали или еднакви на неа (ова ќе ни помогне да одредиме каде завршуваат шестките во замислената низа од сите подредени броеви). Едноставно, во низата 3,4,5,5,6,6,7,7,8,8,9,9,10 постојат шест броеви помали или еднакви на 6 (3, 4, 5, 5, 6, 6), па знаеме точно каде завршуваат шестките, и почнуваат поголемите броеви. Користејќи го овој начин на одредување на позициите, може да искористиме бинарно пребарување за пронаоѓање на вредноста која се наоѓа на X-тата позиција.

Во продолжение е даден кодот кој го решава овој проблем. Како помошна функција, ја имаме countSmallerOrEqual(intervals, K), која што ќе ни кажува колку броеви се помали или еднакви на K. Потоа, само спроведуваме бинарно пребарување, земајќи во предвид две променливи кои ни ги означуваат границите на интервалот од вредности кој сеуште се разгледува (left и right). Едната вредност (left) ни покажува на најголемиот број што сме го разгледале, а кој не ги исполнува условите да има доволно броеви (помали или еднакви) за тој да се наоѓа на X-тата позиција; додека right ни покажува на најмалиот број кој сме го разгледале и кој го исполнува тој услов. Нормално, резултатот кој го бараме по завршување на алгоритамот за бинарно пребарување е токму оној во променливата right - т.е., циклусот ќе запре кога left и right ќе се разликуваат за еден (условот left + 1 < right нема да е исполнет), а бидејќи left ни покажува на несоодветна вредност, right е одговорот кој го бараме.

Доколку сеуште не ви е јасно, да замислиме дека го бараме бројот на позиција X=3, и нека при извршување на алгоритамот дојдеме до ситуација каде left=4, right=5, и соодветно countSmallerOrEqual(intervals, 4) = 2, и countSmallerOrEqual(intervals, 5) = 4. Од тука, можеме да видиме дека броевите на третата и четвртата позиција се еднакви на 5, бидејќи постојат два броја помали или еднакви на 4, а четири броја помали или еднакви на 5.

//koristi C++11 - http://mendo.mk/Lecture.do?id=26

int countSmallerOrEqual(vector<pair<int, int> > &intervals, int K)
{
     int counter = 0;
     
     for (auto interval : intervals)
     {
          if(K >= interval.first)
          {
               if(K > interval.second)
               {
                    //K e pogolem od site broevi vo intervalot
                    counter += interval.second - interval.first + 1;
               }
               else
               {
                    //zemi del od intervalot
                    counter += K - interval.first + 1;
               }
          }
     }
     
     return counter;
}


int findXth(vector<pair<int, int> > &intervals, int X)
{
     int minValue = intervals[0].first;
     for (auto interval : intervals)
     {
          //odredi go najmaliot broj koj se sodrzhi vo intervalite
          //shto, normalno, kje bide pochetok na eden interval (tamu se najmalite)
          minValue = min(minValue, interval.first);
     }
     
     int maxValue = intervals[0].second;
     for (auto interval : intervals)
     {
          //odredi go najgolemiot broj koj se sodrzhi vo intervalite
          //shto, normalno, kje bide krajot na eden interval (tamu se najgolemite)
          maxValue = max(maxValue, interval.second);
     }
     
     //sega, izvrshi go algoritamot za binarno prebaruvanje
     //najprvo, pochni so dvata uslovi za kraevite na intervalot
     if(countSmallerOrEqual(intervals, minValue) >= X)
     {
          //ima povekje od (X) pojavuvanja na "minValue"
          //pa elementot na X-tata pozicija e "minValue"
          //bidejki nizata e podredena, pa minValue se
          //naogja na pocetokot od nea
          return minValue;
     }
     
     if(countSmallerOrEqual(intervals, maxValue) < X)
     {
          //nema dovolno elementi, bidejki duri i ako
          //ja koristime "maxValue" za broenje, shto znachi deka
          //kje izbroime sve, togash pak kje ima
          //pomalku od X elementi
          return -1;
     }
     
     int left = minValue, right = maxValue;
     while(left + 1 < right)
     {
          int middle = (left + right) / 2;
          if(countSmallerOrEqual(intervals, middle) < X)
          {
               //treba da barame pogolemi vrednosti
               left = middle;
          }
          else
          {
               //treba da barame pomali vrednosti
               right = middle;
          }
     }
     
     //"right" e vrednosta koja ja barame
     return right;
}

Задачата која што ја разгледавме е доста интересна, но и доста сложена за разбирање. Сепак, целта на ова предавање беше да се запознаеме со моќта на бинарното пребарување, и да сфатиме дека истото може да се искористи за решавање на разни проблеми.

Дозвола за користење: CC BY-NC 2.5 ©