Бинарна претрага

Увод

Поред сортирања, бинарна претрага је један од најважнијих алгоритама у рачунарству. Користи се за ефикасно претраживање елемената у сортираном низу. Сортираност улазног низа је кључни предуслов за примену бинарне претраге и не сме се игнорисати. Уколико улазни подаци нису сортирани, бинарна претрага се не сме користити, већ се мора користити линеарна претрага. Такође, пре примене бинарне претраге морамо да знамо да ли је низ сортиран растуће или опадајуће.

Алгоритам је заснован на техници подели па владај. Крећемо од дефинисања леве $l$ и десне границе претраге $d$ . На почетку лева граница ће бити индекс $l = 0$ , а десна граница ће бити последњи индекс, тј. $d = n-1$ . У свакој итерацији одређујемо средишњи индекс $m = l + (d-l)/2$ и упоређујемо елемент на тој позицији са траженим елементом $x$ . Ако смо елемент нашли, прекидамо претрагу и враћамо његову позицију, тј $m$ . Ако елемент нисмо нашли, претрагу настављамо у левој или десној половини простора претраге у зависности од тога да ли је тражена вредност $x$ мања или већа од елемента на средишњем индексу.

Временска сложеност бинарне претраге је $О(\log n)$ , при чему је $n$ број елемената у низу. Просторна сложеност алгоритма бинарне претраге је константна.

Једноставна имплементација бинарне претраге на растуће сортираном низу је у наставку:

static int binarna_pretraga(int[] niz, int x) 
{
    int l = 0;
    int d = niz.Length - 1;
    while (l < d) {
        int m = l + (d-l)/2;
        if (niz[m] == x)
            return m;
        else if (niz[m] < x)
            l = m + 1;
        else 
            d = m - 1;
    }
    return -1;
}

У имплементацији је важно приметити линију 6 обележену жутом бојом. Одређивање средишњег индекса у низу се никада не ради као аритметичка средина леве и десне границе због ризика од прекорачења, већ се увек ради на начин који је приказан овде. Поред ове линије, треба обратити пажњу и на линије 10 и 12 које ажурирају границе простора претраге. Умањивање и увећавање средишњег индекса је неопходно да се претрага не би заглавила, а оправдано је тиме што смо средишњи елемент већ испитали и нема потребе да се њиме бавимо опет. Иако по природи рекурзиван алгоритам, бинарна претрага се увек имплементира итеративно.

Када се ради о елементарним претрагама, не морамо да имплементирамо бинарну претрагу сваки пут, већ можемо да користимо уграђени метод. Програмски језик C# обезбеђује уграђени метод BinarySearch над низовима и листама који ради на врло сличан начин као и уграђени метод Sort. Од нас се очекује да наведемо који елемент тражимо у низу/листи и евентуално прилагођени упоређивач ако се ради о сложеним типовима података. Повратна вредност метода BinarySearch је цео број који носи две информације:

Ако се елемент налази у низу, тада метод враћа његов индекс, тј. ненегативан цео број.
Ако се елемент не налази у низу, тада метод враћа негативан број. Овај негативан број није било какав, већ представља битовски комплемент првог елемента у низу који је већи од траженог.

Бинарна претрага се често комбинује са сортирањем улазних података као уобичајена техника за снижавање временске сложености алгоритама са квадратне, на логлинеарну.

Бинарна претрага преломне тачке

До сада смо описали најосновнији облик бинарне претраге који се може лако уопштити. Kао својство за поделу нашег проблема користили смо услов $\ge x$ , при чему је $x$ број који смо у низу тражили. На тај начин смо сортирани низ поделили на две дисјунктне групе, тј. групу $A$ која не испуњава услов $\ge x$ , праћену групом $B$ која испуњава услов. Шематски, то можемо да прикажемо као

$-----++++++++$

где су са $-$ означени елементи који немају, а са $+$ елементи који имају својство $\ge x$ .

Уопштење овог случаја се може лако извести дозвољавањем да услов поделе буде неки произвољни логички израз $P$ . Важно је то да услов $P$ дели наш низ на две дисјунктне групе које се не преклапају, тј дозвољене су поделе облика

$-----++++++++$

или

$++++++++-----$ .

Такође, дозвољена је и ситуација у којој је било која од група празна. Важно је напоменути да сортираност елемената у општем случају није неопходна. Довољно је само да постоји подела на две групе које се не преклапају.

Својство $P$ може бити сасвим произвољно. На пример, низ ученика може бити организован тако да су прво наведени дечаци, а затим девојчице, а својство $P$ може бити пол ученика.

Бинарна претрага нам може помоћи да ефикасно одредимо преломну тачку (енгл. turning point), тј. место где престаје једна и почиње друга група елемената. То може бити или позиција последњег елемента који нема својство $P$ или првог елемента који има својство $P$ . Ако сви елементи низа имају својство $P$ , тада претрага за позицијом последњег елемента низа који нема својство треба да врати $−1$ . Ако ниједан елемент низа нема својство $P$ , тада претрага за позицијом првог елемента низа који има својство $P$ треба да врати дужину низа. Познавање преломне тачке нам омогућава и да ефикасно одговоримо на питање колико је елемената у свакој групи (колико елемената низа нема, а колико елемената низа има својство $P$ ).

Класична бинарна претрага се лако формулише као претрага преломне тачке. Ако у низу пронађемо позицију првог елемента који је већи или једнак траженој вредности $x$ , тада можемо проверити да ли је та позиција унутар низа (строго мања од дужине низа) и да ли се на њој налази елемент $x$ - ако је то испуњено елемент постоји у низу, а у супротном не постоји.

Бинарна претрага преломне тачке се користи у случајевима када је потребно да одредимо први или последњи елемент низа који испуњава или не испуњава неки услов. Због општости услова $P$ , бинарну претрагу преломне тачке је најчешће потребно ручно имплементирати.

Бинарна претрага оптималне вредности

Бинарна претрага се може употребити и у процесу оптимизације, тј. као механизам за решавање проблема облика одредити максималну или минималну вредност која задовољава одређени услов. Важно је одмах на почетку напоменути да се не могу сви оптимизациони проблеми решавати бинарном претрагом. Да бисмо проблем могли да решимо бинарном претрагом морају да буду испуњени следећи услови:

Проблем је могуће превести у проблем одлучивања - У пракси то значи да задатак облика наћи најмању/највећу вредност која задовољава услов можемо да сведемо на давање одговора на питање да ли дата вредност задовољава услов / да ли је дата вредност решење проблема. Дакле, проблем сводимо на систематску претрагу у простору решења проблема.
Монотоност - Ако нека вредност $x$ задовољава услов, онда свака вредност већа од $x$ задовољава услов када се ради о минимизацији. У случају максимизације, онда свака вредност мања од $x$ мора задовoљавати услов. Приметимо да нам монотоност омогућава да проблем сведемо на проблем бинарне претраге преломне тачке у простору решења.
Могуће је лако проверити да ли је дата вредност решење проблема - Постоји ефикасна функција, обично линеарне или ниже временске сложености, која за дату вредност $x$ испитује да ли је решење проблема или не.

Одавде треба закључити да претрагу не вршимо по индексима низа, већ по могућим кандидатима за решење проблема, док полазни низ користимо само да проверимо да ли је тај кандидат решење или не. Због тога, чест назив за овакав облик претраге је и бинарна претрага по решењу.

С обзиром да бинарна претрага оптималне вредности врши претрагу у простору решења проблема, а не у датом низу вредности, морамо је увек ручно имплементирати и имплементација увек прати следећи шаблон:

Испитати да ли се проблем може превести у проблем одлучивања и да ли је монотон.
Осмислити алгоритам којим се проверава да ли је дата вредност решење или не.
Одредити опсег могућих решења.
Применити бинарну претрагу на опсег кандидата решења. Метод из корака 2 користимо за усмеравање претраге и одсецање у простору решења.

Корак 1 не смемо да прескачемо нити да подразумевамо. Уколико проблем не испуњава услове, бинарна претрага оптималне вредности се не може применити као механизам његовог решавања.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

У продавници се налази пуно врста производа и познати су њихови бар-кодови. Произвођач жели да сазна колико се врста његових производа продаје у тој продавници. Ако је списак свих кодова производа у про- давници дат у сортираном облику, а списак свих кодова производа произвођача је достављен несортиран, написати програм који одређује тражени број.

Улаз: Са стандардног улаза учитава се број $n$ ( $1 \le n \le 50000$ ), a затим $n$ природних бројева (највише шестоцифрених), раздвојених размацима. Ти бројеви представљају бар-кодове производа у продавници и сортирани су растуће. Након тога се до краја улаза учитавају бар-кодови производа које је произвођач доставио (највише шестоцифрени природни бројеви, сваки у посебном реду).

Излаз: На станадрни излаз исписати број производа произвођача који се већ продају у продавници.

Решење

Наивно, задатак бисмо могли да решимо линеарним претраживањем једног по једног произвођачевог бар-кода у сортираном низу бар-кодова у продавници. Такво решење има временску сложеност $O(n^2)$ .

Ефикасније решење бисмо добили применом бинарне претраге. Полазни низ је сортиран, па је примена оправдана. У решењу ћемо користити уграђени метод BinarySearch који стрингове подразумевано упоређује лексикографски.

static int zad1(string[] sviKodovi, string[] kodoviProizvodjaca) 
{
    int uPonudi = 0;
    for (int i = 0; i < kodoviProizvodjaca.Length; i++) 
    {
        int retVal = Array.BinarySearch(sviKodovi, kodoviProizvodjaca[i]);
        if (retVal >= 0)
            uPonudi += 1;
    }
    return uPonudi;
}

Временска сложеност приказаног решења је $O(k \log n)$ , при чему $k$ представља број произвођачевих бар-кодова и $n$ представља укупан број бар-кодова у понуди продавнице. Претпостављамо да су сви бар кодови исте величине, па је упоређивање два бар кода константа операција која не зависи од броја бар-кодова у понуди.

Задатак 2

Дат је цео број $s$ и низ различитих целих бројева. Написати програм којим се одређује број парова у низу који имају збир једнак датом броју $s$ .

Улаз: У првој линији стандардног улаза налази се цео број $s$ (број из интервала $[0, 10^6]$ ), у другој линији налази се број елемената низа $n$ ( $1 \le n \le 50000$ ), а у следећих $n$ линија налазе се редом елементи низа (бројеви из интервала $[0, 10^6]$ ).

Излаз: На стандардном излазу приказати број парова различитих елемената низа чији је збир једнак броју $s$ .

Решење

Наивно, задатак можемо да решимо упоређивањем збирова свих парова елемената у низу са траженим збиром. Решење се своди на једноставну двоструку петљу:

static int zad2(int[] niz, int s) 
{
    int br = 0;
    for (int i = 0; i < niz.Length; i++) 
    {
        for (int j = i + 1; j < niz.Length; j++) 
        {
            if (niz[i] + niz[j] == s) 
            {
                br = br + 1;
            }
        }
    }
    return br;
}

Временска сложеност приказаног решења је $O(n^2)$ .

Ако пажљиво прочитамо задатак, јасно је да за сваки елемент у низу $a_i$ треба да пронађемо елемент $s - a_i$ . Дакле, наш програм се своди на $n$ претрага. Једини начин да наш програм учинимо ефикаснијим је да претрагу учинимо ефикаснијом. Претрага може бити ефикаснија само ако применимо бинарну претрагу, што захтева да прво сортирамо улазни низ. Сортирање улазног низа је операција чија је временска сложеност $O(n \log n)$ . Након сортирања треба да применимо $n$ бинарних претрага, чија ће укупна сложеност бити $O(n \log n)$ . Дакле, укупна сложеност решења ће бити $O(n \log n)$ . Решење је у наставку:

static int zad2_efikasnije(int[] niz, int s) 
{
    Array.Sort(niz);
    int br = 0;
    for (int i = 0; i < niz.Length; i++) 
    {
        int retVal = Array.BinarySearch(niz, s - niz[i]);
        if (retVal >= 0 && retVval != i) 
            br = br + 1;
    }
    return br;
}

Приметимо услов у линији 8 која је обележена жутом бојом. Није довољно само да пронађемо број $s - a_i$ , већ морамо да осигурамо да се пронађени број не налази на позицији $i$ . Приказани поступак је стандардни начин којим се квадратни алгоритам своди на логлинеарни. Чим задатак можемо да сведемо на велики број претрага, готово увек је прва идеја за снижавање сложености сортирање праћено применом бинарне претраге.

Задатак 3

Напиши програм који проверава да ли у строго растућем низу елемената постоји позиција $i$ таква да се на позицији $i$ налази вредност $i$ тј. да важи да је $a_i = i$ (позиције се броје од нуле).

Улаз: Са стандардног улаза се уноси број $n$ ( $0 \le n \le 10^5$ ), а затим и строго растући низ од $n$ целих бројева (сваки у посебном реду).

Излаз: На стандардни излаз исписати индекс $i$ такав да је $a_i = i$ или текст nema ако такав индекс не постоји у низу. Ако у низу постоји више таквих индекса исписати најмањи од њих.

Решење

Задатак директно можемо решити линеарном претрагом, што није никакав изазов. У петљи ћемо испитивати да ли је $a_i = i$ и ако јесте прекинућемо петљу и вратићемо индекс на којем се број налази. Ако не нађемо елемент који испуњава дати услов, вратићемо -1. Временска сложеност наивног решења је $O(n)$ . Имплементацију наивног решења остављамо читаоцу за вежбу.

Задатак се може решити и применом бинарне претраге. Треба само да искористимо чињеницу да је улазни низ сортиран. Ефиксаније решење можемо добити ако приметимо следеће:

Низ је сортиран.
Услов $a_i = i$ можемо да преведемо у $a_i - i = 0$ .
Потребно је да трансформишемо низ према претходном закључку и да бинарном претрагом у сортираном низу пронађемо вредност 0.

Решењe je у наставку:

static  zad3_v2() 
{
    int n = int.Parse(Console.ReadLine())
    int[] niz = new int[n];
    // трансформација у фази учитавања не утиче на сложеност алгоритма
    for (int i = 0; i < niz.Length; i++) {
        niz[i] = int.Parse(Console.ReadLine()) - i;
    }
    int retVal = Array.BinarySearch(niz, 0)
    return retVal < 0 ? - 1 : retVal;
}

Ово решење иако примамљиво, има смисла само ако ову трансформацију учинимо приликом учитавања низа. Ако трансформацију радимо након учитавања, тада ће временска сложеност трансформације доминирати над претрагом и решење ће опет бити линеарне временске сложености, иако користимо бинарну претрагу. Неефикасно решење које користи бинарну претрагу је у наставку:

static bool zad3_v3(int[] niz) 
{
    // трансформација постојећег низа утиче на сложеност алгоритма
    for (int i = 0; i < niz.Length; i++) {
        niz[i] = niz[i] - i;
    }
    int retVal = Array.BinarySearch(niz, 0)
    return retVal < 0 ? - 1 : retVal;
}

Задатак можемо да решимо у логаритамском времену без икакве трансфоримације низа. Потребно је само да приметимо следеће:

Низ је сортиран растуће.
Вредности у низу расту једнаком или већом брзином од вредности индекса.
У сваком кораку можемо да упоређујемо средишњи индекс са вредности на том месту, тј. упоређујемо amida_{\text{mid}} и mid\text{mid}:
- Ako je $a_{\text{mid}} = \text{mid}$ , нашли смо решење
- Ako je $a_{\text{mid}} < \text{mid}$ , тада претрагу настављамо у десној половини низа. Низ је строго растући, па на свим позицијама лево од $\text{mid}$ могу бити само вредности које су још мање у односу на своје индексе, па тражено решење, ако постоји, мора бити десно од текуће средње позиције.
- Ako je $a_{\text{mid}} > \text{mid}$ , тада претрагу настављамо у левој половини низа. Аналогно објашњење важи као у претходном случају.

У овој идеји постоји само један проблем. Вредност коју тражимо се мења у свакој итерацији бинарне претраге. Због тога не можемо да користимо уграђени метод BinarySearch(), већ морамо да имплементирамо своју прилагођену бинарну претрагу. Решење је у наставку:

static int zad3_efikasno(int[] niz) 
{
    int l = 0;
    int d = niz.Length - 1;
    while (l < d) {
        int m = l + (d - l)/2;
        if (niz[m] == m)
            return m;
        else if (niz[m] < m)
            l = m + 1;
        else 
            d = m - 1;
    }
    return -1;
}

Временска сложеност приказаног решења је $O(\log n)$ .

Задатак 4

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

Улаз: Са стандардног улаза учитава се број $n$ ( $1 \le n \le 50000$ ), а затим $n$ линија које садрже парове природних бројева мањих од $10^6$ раздвојене са по једним размаком, а који представљају положај (удаљеност од врха странице) горње и доње ивице $n$ објеката са странице. Објекти су поређани неопадајуће у односу на положај њихове горње ивице.

Након тога се уноси број $m$ ( $1 \le m \le 50000$ ), a затим $m$ парова природних бројева раздвојених са по једним размаком (њих највише $50000$ ) који представљају положај (удаљеност од врха странице) горње и доње границе видљивог дела странице.

Излаз: За сваки пар бројева који одређују видљиви део странице на стандардни излаз исписати по једну линију која садржи два цела броја раздвојена размаком. Први број представља позицију (индекс унутар низа, бројано од нуле) првог објекта чији је положај горње ивице строго већи од положаја горње границе видљивог дела странице, а други број представља позицију последњег објекта чији је положај горње ивице строго мањи од положаја доње границе видљивог дела странице. Ако се горње ивице свих објеката у низу налазе изнад горње границе видљивог дела, први број треба да буде једнак n. Ако се горње ивице свих објеката у низу налазе испод доње границе, други број треба да буде $-1$ .

Решење

Из текста задатка се лако уочава да нам доње ивице објеката на екрану нису важне. Објекте приказујемо на екрану само ако им је горња ивица у видљивом делу екрана. Због тога, не морамо да правимо посебан тип који представља објекте, већ можемо да их поистоветимо са њиховом горњом границом. Да бисмо решили задатак треба да пронађемо први објекат чија је горња коодрината већа или једнака горњем положају текућег екрана, као и последњи објекат чија је горња координата мања или једнака доњем положају текућег екрана. Наивна идеја би била да за сваки положај екрана, тражене координате објеката пронађемо линеарном претрагом.

static int prvi_veci(int[] gornjeIvice, int x) 
{
    for (int i = 0; i < gornjeIvice.Length; i++) 
    {
        if (gornjeIvice[i] > x)
            return x;
    }
    return gornjeIvice.Length;
}
static int poslednji_manji(int[] gornjeIvice, int x) 
{
    for (int i = 0; i < gornjeIvice.Length; i++)     
    {
        if (gornjeIvice[i] >= x)
            return i - 1;
    }
    return gornjeIvice.Length - 1;
}
static void zad4(int[] gornjeIviceObjekata, int[] gornjeIviceEkrana, int[] donjeIviceEkrana) {
    for (int i = 0; i < gornjeIviceEkrana.Length; i++) {
        int prvi = prvi_veci(gornjeIviceObjekata, gornjeIviceEkrana[i]);
        int poslednji = posledni_manji(gornjeIviceObjekata, donjeIviceEkrana[i]);
        Console.WriteLine("{0} {1}", prvi, poslednji);
    }
}

За сваки положај екрана покрећемо две линеарне претраге, чија је сложеност $O(n)$ , па ће укупна сложеност оваквог решења бити $O(2mn) \approx O(n^2)$ . Задатак можемо да решимо и ефикасније, тј. у временској сложености $O(2m \log n) \approx O(n \log n)$ .

Потребно је да уочимо да је низ у којем претражујемо координате сортиран неопадајуће по горњој координати. С обзиром да тражимо у сортираном низу можда бисмо могли да искористимо бинарну претрагу. Слично као и малопре, применићемо две бинарне претраге.

Првом бинарном претрагом, одредићемо први објекат чија је горња граница већа или једнака горњој координати текућег положаја екрана. Јасно је да се ради о бинарној претрази преломне тачке са условом P = горња граница објекта већа или једнака од горње координате екрана. Тиме добијамо партицију полазног низа координата која је облика

$-----------++++++++++++++++$

и треба да одредимо индекс првог плуса.

Другом бинарном претрагом, одредићемо последњи објекат чија је горња граница мања или једнака доњој координати текућег положаја екрана. Јасно је да се ради о бинарној претрази преломне тачке са условом P = горња граница објекта мања или једнака од доње координате екрана. Тиме добијамо партицију полазног низа координата која је облика

$+++++++++++++++++++++------$

и треба да одредимо индекс последњег плуса.

Решење које користи бинарну претрагу је у наставку:

static int prvi_veci_bp(int[] gornjeIvice, int x) 
{
    int l = 0
    int d = gornjeIvice.Length;
    while (l < d) 
    {
        int m = l + (d-l)/2;
        if (gornjeIvice[m] > x)
            d = m;
        else
            l = m + 1;
    }
    return d;
}
static int poslednji_manji_bp(int[] gornjeIvice, int x) 
{
    int l = 0
    int d = gornjeIvice.Length;
    while (l < d) 
    {
        int m = l + (d-l)/2;
        if (gornjeIvice[m] >= x)
            d = m;
        else
            l = m + 1;
    }
    return d - 1;
}
static void zad4_efikasno(int[] gornjeIviceObjekata, int[] gornjeIviceEkrana, int[] donjeIviceEkrana) {
    for (int i = 0; i < gornjeIviceEkrana.Length; i++) {
        int prvi = prvi_veci_bp(gornjeIviceObjekata, gornjeIviceEkrana[i]);
        int poslednji = posledni_manji_bp(gornjeIviceObjekata, donjeIviceEkrana[i]);
        Console.WriteLine("{0} {1}", prvi, poslednji);
    }
}

Иако се ради о бинарној претрази, обратите пажњу на управљање границама простора претраге у обележеним линијама. Управљање границама се увек мора прилагодити проблему који се решава и кључно је за добијање исправних резултата. Бинарна претрага преломне тачке је општији поступак од обичне бинарне претраге и то увек треба да имате на уму приликом имплементирања решења.

Временска сложеност и једне и друге бинарне претраге је $O(\log n)$ . Треба да извршимо $2m$ бинарних претрага, па ће укупна временска сложеност програма бити $O(2m \log n) \approx O(n \log n)$ . Просторне сложености и наивног и ефикасног решења су константне.

Задатак 5

Државна комисија треба да одреди праг за пролазак такмичара са окружног на државно такмичење. Пошто је информатика постала обавезан предмет у основним школама, број такмичара је јако велики. Администра- торку Мају која одржава табелу са резултатима стално питају који би број такмичара прошао даље када би праг пролазности био толико и толико поена (даље се пласирају сви ученици чији је број поена већи или једнак прагу). Одлучила је да напише програм који даје одговор на та питања.

Улаз: Са стандардног улаза учитава се број такмичара $n$ ( $0 \le n \le 10^5$ ), а затим и поени такмичара (цели бројеви), задати у сортираном редоследу од највећег до најмањег. Након тога се учитава број $m$ ( $1\le m \le 50000$ ) који представља број питања на која Маја треба да одговори, а затим и $m$ бројева за које је потребно дати одговор колико би се такмичара пласирало када би се тај број узео за праг. Сваки број се налази у посебном реду.

Излаз: На стандардни излаз исписати тражене бројеве пласираних такмичара, сваки у посебном реду.

Решење

Задатак се може директно решити применом линеарне претраге за свако од $m$ питања. Временска сложеност оваквог решења би била $O(mn)$ . Наивно решење нећемо даље разматрати и препуштамо га читаоцу за вежбу.

Ефикасније решење можемо добити ако искористимо услов из задатка. Улазни подаци су већ сортирани према броју поена, па бисмо могли да користимо бинарну претрагу. За сваки упит, треба да пронађемо први мањи број освојених поена. Прецизније имамо поделу улазног низа облика

$++++++++++++---------------.$

Након што пронађемо тражени индекс, број награђених биће једнак индексу првог мањег броја. Разлог више да користимо бинарну претрагу преломне тачке је велики број упита на које треба да одговоримо, тј. велики број претрага које треба да извршимо. Ефикасно решење је у наставку:

static int prvi_manji(int[] poeni, int x) 
{
    int l = 0
    int d = poeni.Length;
    while (l < d) 
    {
        int m = l + (d-l)/2;
        if (poeni[m] >= x)
            l = m + 1;
        else
            d = m;
    }
    return d;
}
static void zad5_efikasno(int[] poeni, int[] upiti) {

    for (int i = 0; i < upiti.Length; i++) {
        int indeks = prvi_manji(upiti, poeni[i]);
        Console.WriteLine(poeni.Length - indeks);
    }
}

Као и у претходном задатку, обратите пажњу на управљање границама у бинарној претрази, као и на прилагођавање бинарне претраге структури улаза и ономе што у низу тражимо.

Временска сложеност ефикасног решења је $O(m \log n)$ . Просторне сложености и наивног и ефикасног решења су константне.

Задатак 6

Планинари су се пели на планину и сваких $10$ минута јављали су надморску висину на којој се налазе. Одредити која је висина планине (ако претпоставимо да су планинари јавили и надморску висину и док су се одмарали на врху).

Улаз: Са стандардног улаза се учитава број $n$ ( $3 \le n \le 50000$ ) а затим низ од $n$ различитих бројева таквих да низ прво расте (планинари се пењу), а затим опада (планинари силазе). И лево и десно од висине врха планине постоји бар један број.

Излаз: На стандардни излаз исписати један број који представља висину планине.

Решење

Очигледно је да задатак можемо да решимо линеарном претрагом. Потребно је само да одредимо максимум низа. Временска сложеност оваквог решења је линеарна. Наивно решење препуштамо читаоцу за вежбу и нећемо га даље разматрати.

Задатак можемо да решимо и у логаритамској сложености, тј. применом бинарне претраге преломне тачке. Ако пажљиво анализирамо улазне податке, видећемо да се ради о низу који прво расте, затим опада. Други назив за овакав низ је бимодални низ. Оно што ми треба да урадимо јесте одређивање преломне тачке, тј. места где низ престаје да расте и почиње да опада.

Логика претраге је следећа:

У сваком кораку претраге одређујемо средишњи индекс $m$ .
Упоређујемо елемент на позицији mm у низу са елементом на позицији m+1m+1. Добијамо један од два случаја:
- Ако је $a_{m} < a_{m+1}$ , то значи да смо још увек на узлазној путањи и да максимум мора бити десно од нас.
- Ако је $a_{m} > a_{m+1}$ , то значи да смо још увек на силазној путањи и да максимум мора бити лево од нас.

Приметимо да у описаном поступку не тражимо конкретну вредност, већ претрагу извршавамо док се границе не поклопе. У тексту задатка је експлицитно наведено да су сви бројеви различити и да низ прво расте, па затим опада, одакле лако закључујемо да постоји тачно један врх, тј. максимум. Решење је у наставку:

static int zad6_efikasno(int[] visine) {
    int l = 0;
    int d = visine.Length - 1;
    while (l < d) {
        int m = l + (d-l)/2;
        if (visine[m] < visine[m + 1])
            l = m + 1;
        else 
            d = m;
    }
    return visine[d];
}

Као и до сада обратите пажњу на управљање границама претраге. Временска сложеност решења је логаритамска, а просторна сложеност је константна.

Задатак 7

Сортирани низ целих бројева у коме су сви елементи различити је ротиран за $k$ места улево и тиме је добијен циклични низ који задовољава услов да је $x_k < x_{k+1} < \ldots < x_{n−1} < x_0 < \ldots < x_{k−1}$ Један такав низ је, на пример, $11 \quad 13 \quad 15 \quad 19 \quad 24 \quad 1 \quad 3 \quad 8 \quad 9$ . Напиши програм који проналази најмањи елемент таквог низа.

Улаз: Са стандардног улаза се учитава број $n$ ( $1 \le n \le 50000$ ), а затим $n$ елемената низа (сваки у посебном реду).

Излаз: На стандардни излаз исписати најмањи елемент низа.

Решење

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

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

Слично као у претходном задатку, не тражимо конкретну вредност, већ упоређујемо средишњи елемент са нечим што може да усмери нашу претрагу и каже нам да ли се наш минимум налази лево или десно од средишњег елемента. Потребно је да пронађемо неки услов који ће увек моћи да нам да одговор да ли је преломна тачка лево или десно независно од тога који индекс да изаберемо као средишњи.

Из услова задатка и дефиниције улазних података, може се уочити следеће:

Ако изаберемо било који елемент из сортираног префикса, тј. лево од преломне тачке, он ће бити већи од последњег елемента у низу.
Ако изаберемо било који елемент из сортираног суфикса, тј. десно од преломне тачке, он ће бити мањи од последњег елемента у низу.

Дакле, након овог запажања можемо лако да конструишемо бинарну претрагу преломне тачке. Изабрани средишњи елемент треба само да упоредимо са последњим елементом дела низа који разматрамо. Ако је изабрани средишњи елемент већи, тада се преломна тачка налази десно од изабраног елемента. Ако је изабрани средишњи елемент мањи, тада се преломна тачка налази лево од изабраног елемента. У задатку треба уочити и специјални случај, а то је циклично померање за $k=0$ , тј. сортиран низ. У том случају не треба да вршимо претрагу. Ефикасно решење је у наставку:

static int zad6_efikasno(int[] niz) {
    int l = 0;
    int d = niz.Length - 1;
    // провера специјалног случаја
    if (niz[l] < niz[d])
        return niz[l];
    // бинарна претрага преломне тачке
    while (l < d) {
        int m = l + (d-l)/2;
        if (niz[m] > niz[d])
            l = m + 1;
        else 
            d = m;
    }
    return niz[d];
}

Задатак 8

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

Улаз: Са стандардног улаза се учитава број дрвећа у шуми $n$ ( $1 \le n \le 10^5$ ), а затим низ висина сваког дрвета (низ природних бројева између $1$ и $10000$ , сваки у посебном реду). Након тога учитава се и количина дрвета које треба исећи (пошто су сва дебла исте дебљине, количина се мери у метрима висине исечених стабала).

Излаз: На стандардни излаз исписати тражену максималну целобројну висину тестере.

Решење

Из текста задатка ми треба да одредимо највећу могућу висину тестере, тако да дрвосеча добије довољну количину дрвета. Јасно је да неке висине тестере могу дати довољну количину дрвета, а неке висине тестере не могу. Дакле, одавде видимо да се проблем заправо директно преводи у проблем одлучивања, тј. треба да дамо одговор на питање Да ли је дата висина тестере $\mathbb{s}$ решење проблема?.

Такође, лако се уочава да је наш проблем монотон, тј. да важи следеће:

Ако је висина тестере $s$ решење проблема, тада су и све висине $x < s$ такође решење проблема.
Ако висина тестере $s$ није решење проблема, тада нису решење ни све висине $y > s$ .

Дакле, монотоност нам гарантује поделу простора решења која се шематски може приказати као

$++++++++++++++-----------------.$

Одавде лако закључујемо да проблем можемо решити бинарном претрагом преломне тачке у простору решења. Потребно је само да осмислимо поступак којим проверавамо да ли је конкретна висина тестере $s$ решење или не, затим да одредимо могући опсег вредности решења и да бинарном претрагом преломне тачке одредимо највишу вредност тестере која нам даје довољну количину дрвета.

static bool da_li_je_resenje(int[] visine, int s) {
    int z = 0;
    for (int i = 0; i < visine.Length; i++) 
    {
        z += Math.Max(visine[i] - s, 0);
    }
    return z >= 0;
}
static int odredi_maksimum(int[] visine) {
    int m = visine[0];
    for (int i = 1; i < visine.Length; i++) 
    {
        if (visine[i] > m)
            m = visine[i];
    }
    return m;
}
static int zad8_efikasno(int[] visine, int s) 
{
    // тестеру не можемо поставити ниже од 0, нити више
    // од висине највишег стабла
    int l = 0;
    int d = odredi_maksimum(visine); 
    // примењујемо бинарну претрагу преломне тачке
    while (l <= d) {
        int m = l + (d-l)/2;
        if (da_li_je_resenje(visine, m))
            l = m + 1;
        else
            d = m - 1;
    }
    return d;
}

На крају, важно је још једном нагласити да бинарну претрагу извршавамо у простору решења, а не у улазним подацима. Улазне податке користимо само за проверу да ли је кандидат за решење заиста решење или не, чиме усмеравамо претрагу у простору решења (линија 27). Такође, треба нагласити да овакво решење има смисла, јер проверу да ли је дати кандидат $s$ решење проблема можемо да урадимо у линеарном времену. Временска сложеност приказаног решења је $O(n \log n)$ , док је просторна сложеност константна.

Задатак 9

Током једног дана конференције одржава се $n$ предавања. Представља се $m$ рачунарских компанија које су означене бројевима од $1$ до $m$ , при чему неке компаније држе и више предавања. Један од учесника конференције жели да присуствује предавањима свих компанија без напуштања сале за предавања. Написати програм који одређује који је најмањи број предавања које мора да одслуша да би чуо све компаније.

Улаз: На стандардном улазу у првом реду је број компанија $m$ ( $1 \le m \le 50$ ), у другом реду је укупан број предавања $n$ ( $1 \le n \le 50000$ ), а у трећем је наведен редослед предавања компанија тако што су наведени њихови редни бројеви (од $1$ до $m$ ) раздвојени размацима.

Излаз: Најмањи број предавања које учесник треба да одслуша у континуитету да би чуо бар по једно предавање сваке компаније. Ако није могуће да учесник одслуша предавање сваке компаније, исписати текст ne moze (без наводника).

Решење

Из текста задатка је јасно да се ради о проблему оптимизације и да треба да одредимо најмањи број предавања које треба одслушати да би се одслушала предавања свих компанија. Проблем се лако пребацује у проблем одлучивања, тј. треба осмислити ефикасан начин да проверимо да ли је предложени број предавања $k$ довољан да се одслушају предавања свих компанија.

Монотоност је такође очигледна. Ако је број $k$ решење проблема, онда ће бити и сваки други број већи од $k$ . Ако број $k$ није решење, онда неће бити ни било који број мањи од $k$ . Ово нам даје поделу простора претраге коју можемо приказати као

$----------++++++++++++++++++$

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

За разлику од претходног задатка, овде је изазов осмислити ефикасни метод за проверавање да ли је кандидат $k$ решење проблема. Да бисмо то испитали, треба да испитамо све сегменте дужине $k$ у полазном распореду предавања. То можемо најефикасније да урадимо применом покретног прозора и одржавањем броја различитих предавања које је слушалац одслушао. Решење је у наставку:

static bool da_li_je_resenje(int[] raspored, int broj_kompanija, int k) {
    // у низу памтимо колико смо предавања сваке компаније одслушали
    int[] indikatori = new int[broj_kompanija];
    // бројимо колико смо различитих компанија одслушали
    int br_razlicitih = 0;
    // пролазимо кроз комплетан распоред
    for (int i = 0; i < raspored.Length; i++) 
    {
        // ако смо завршили са првим сегментом
        if (i >= k) 
        {
            // прво предавање избацујемо из разматрања
            indikatori[raspored[i - k]]--;
            // ако је то било једино предавање дате компаније
            // смањујемо бројач различитих
            if (indikatori[raspored[i - k]] == 0)
                br_razlicitih -= 1;
        }
        // додајемо предавање текуће компаније
        indikatori[raspored[i]]++;
        // ако се ради о новој компанији, увећавамо бројач различитих
        if (indikatori[raspored[i]] == 1)
            br_razlicitih += 1;
        // ако смо послушали све компаније, завршавамо претрагу
        if (br_razlicitih == broj_kompanija)
            return true;
    }
    // ако смо прошли кроз цео низ и нисмо све одслушали, 
    // онда k није решење проблема
    return false;
}
static int zad9_efikasno(int[] raspored, int broj_kompanija) 
{
    // најмање можемо одслушати једно предавање, а највише сва
    int l = 1;
    int d = raspored.Length; 
    // примењујемо бинарну претрагу преломне тачке
    while (l <= d) {
        int m = l + (d-l)/2;
        if (da_li_je_resenje(raspored, broj_kompanija, k))
            d = m - 1;
        else
            l = m + 1;
    }
    // ако је l == raspored.Length, тада нема решења
    return l;
}

Временска сложеност приказаног решења је $O(n \log n)$ . Цена провере једног кандидата за решење је линеарна, а таквих провера укупно имамо $O(\log n)$ , па одатле следи закључак о укупној сложености. Просторна сложеност је једнака величини помоћног низа у функцији da_li_je_resenje(), тј. броју компанија. Број компанија би требало да буде изузетно мали број у односу на број предавања, па га у пракси можемо сматрати константом.

Да бисмо постигли временску сложеност $O(n \log n)$ , кључно је да проверу решења можемо да урадимо у линеарном времену. То смо обезбедили применом пресликавања, тј. низа индикатора и применом покретног прозора за ефиксано ажурирање карактеристика сегмената. Без ове две технике, решење би било неупоредиво више временске сложености.

Задатак 10

Графички дизајнер је преуредио неколико слова у једном фонту и жели да своје промене прикаже клијенту. У дугачком тексту је потребно да одабере најкраћи део (сегмент узастопних слова) који садржи сва слова која је променио.

Улаз: У првој линији стандардног улаза налази се текст (једноставности ради претпоставимо да је састављен само од малих слова енглеског алфабета) чија је дужина највише $50000$ карактера. У другој линији се налази скуп слова (опет, претпоставимо малих слова енглеског алфабета) које је дизајнер променио (слова су написана једно до другог, без размака и без понављања).

Излаз: На стандардни излаз исписати један цео број који представља дужину најкраћег дела текста који садржи све карактере датог скупа. Ако такав део текста не постоjи, исписати nema.

Решење

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

static bool da_li_je_resenje(string t, HashSet<char> slova, int k) {
    // користимо речник као помоћну структуру података
    Dictionary<char, int> pojavljivanja = new Dictionary<char, int>();
    // пролазимо кроз сва слова у тексту
    for (int i = 0; i < t.Length; i++) 
    {
        // ако смо прешли задату величину сегмента
        if (i >= k) 
        {
            // ако је слово у скупу измењених слова
            // умањујемо број појављивања
            if (slova.Contains(t[i - k])) 
            {
                pojavljivanja[t[i - k]]--;
                // ако нема више појављивања, елиминишемо слово из речника
                if (pojavljivanja[t[i-k]] == 0)
                    pojavljivanja.Remove(t[i - k]);
            }
        }
        // додајемо следеће слово у речник, ако је у скупу измењених слова
        if (slova.Contains(t[i])) 
        {
            int br = 0;
            pojavljivanja.TryGetValue(t[i], out br);
            pojavljivanja[t[i]] = br + 1;
            // након сваког додавања проверавамо да ли смо пронашли сва слова
            if (pojavljivanja.Count == slova.Count)
                return true;
        }
    }
    // ако прођемо кроз цео текст, нисмо нашли сегмент дужине k
    // који садржи сва слова
    return false;
}
static int zad9_efikasno(string t, string s) 
{
    // креирамо хеш скуп због ефикасније провере да ли
    // слово припада скупу измењених слова
    HashSet<char> slova = new HashSet<char>(s);
    int l = 1;
    int d = raspored.Length; 
    // примењујемо бинарну претрагу преломне тачке
    while (l <= d) {
        int m = l + (d-l)/2;
        if (da_li_je_resenje(t, slova, m))
            d = m - 1;
        else
            l = m + 1;
    }
    // ако је l == t.Length, тада нема решења
    return l;
}

Временска сложеност приказаног решења је $O(n \log n)$ . Цена провере једног кандидата за решење је линеарна, а таквих провера укупно имамо $O(\log n)$ , па одатле следи закључак о укупној сложености. Просторна сложеност је једнака броју слова које је дизајнер изменио, јер је ће то бити величина помоћне структуре података коју користимо у функцији da_li_je_resenje(). Као и у претходном задатку, тај број је много пута мањи од величине текста, па у пракси можемо сматрати да се ради о константној сложености.