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

Бинарна претрага
	Бинарно петраживачки низ
Класа	Алгоритам сортирања
Структура података	Низ
Најгора перформанца
Најбоља перформанца
Најгора просторна комплексност

У рачунарству, бинарна претрага или претрага методом половљених интервала је алгоритам проналажења индекса одређеног елемента - кључа у сортираном низу. У сваком кораку, алгоритам упоређује вредност кључа са вредношћу средишњег члана низа. Уколико се вредности подударају, алгоритам се завршава и средишњи елемент је тражени, а самим тим пронађен је и његов индекс у низу. У супротном, уколико је вредност кључа мања од вредности средишњег члана алгоритам се понавља на леви подниз у односу на средишњи елемент. Ако је кључ већи од средишњег члана онда се алгоритам примењује на десни подниз. Алгоритам може да има два исхода, или да пронађе индекс појављивања кључа у сортираном низу или да установи да се у низу не појављује тражени кључ. До другог исхода може доћи оног тренутка када подниз који треба алгоритмом претражити постане празан. Бинарна претрага је један од примера „завади па владај“ алгоритма.

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

Алгоритми Уреди

Рекурзивна верзија

Једноставна верзија бинарног претраживања је рекурзивна. Првобитни позив користи индексе целог низа за претраживање. Потом се поступак преноси на један од два подниза (левог или десног). Рекурзивно се позива бинарна претрага за један подниза. Излаз из рекурзије је када се претрага врши на празном низу.

int binary_search(int A[], int key, int min, int max)
{
  // тражити док се низ не испразни
  if (max < min)
    // ако је низ празан кључ се не може пронаћи
    return KEY_NOT_FOUND;
  else
    {
      // рачунање средишњег елемента
      int mid = midpoint(min, max);
 
      // поређења са кључем
      if (A[mid] > key)
  // кључ је мањи од средишњег, те рекурзивно претражујемо леви подниз
        return binary_search(A, key, min, mid-1);
      else if (A[mid] < key)
        // уколико је већи, претражујемо десни подниз
        return binary_search(A, key, mid+1, max);
      else
        // уколоко су једнаки пронашли смо га
        return mid;
    }
}

Итеративна верзија

int binary_search(int A[], int key, int min, int max)
{
  // вршимо претрагу докле год низ [min,max] није празан
  while (max >= min)
    {
      // рачунамо средишњи елемент
      int mid = midpoint(min, max);
      if(A[mid] == key)
        // проверавамо да ли је кључ једнак средишњем елементу
        return mid; 
      // одлучујемо се за један од поднизова
      else if (A[mid] < key)
        // померамо леву границу 
        min = mid + 1;
      else         
        // померамо десну границу
        max = mid - 1;
    }
  // уколико кључ није нађен
  return KEY_NOT_FOUND;
}

или

int binarna_pretraga (int na, int trazenielement, int a[]) {
    int desni, granica, sredina;
    desni = 0; granica = an - 1;

    while (desni <= granica) {
        sredina = (desni+granica)/2;
        if (a[sredina] == trazenielement) 
            return (sredina);
        if (a[sredina] < trazenielement) desni = sredina+1;
        else ggranica = sredina-1;
    }
    return(-1);
}

Перформансе Уреди

У сваком тесту који не успе да пронађе тражени кључ, претрага се наставља у једном или другом подинтервалу који је дупло мањи по величини од полазног. Тачније, уколико је величина показног интевала N , тада подинтевали садрже по N/2 или N/2-1 елемената.

После прве итерације низ који претражујемо има највише N/2 чланова. У наредној, N/4 и тако даље. У најгорем случају, ако се у низу не налази вредност кључа алгоритам мора да настави претрагу све док не добије празан подниз. У најгорем случају, то ће се догодити за ⌊log_2⁡〖n+1〗 ⌋ корака. Где је ⌊х⌋ нотација која аргумент х заокружује на први мањи цео број. У односу на линерану претрагу, чија је у најгорем случају, сложеност од N итерација. Примећујемо да је бинарна претрага знатно бржа од линеарне. На пример, уколико претражујемо низ од милион чланова, у линеарној претрази бисмо имали исто толико корака, а у бинарној претрази никад више од двадесет итерација. Мана бинарне претраге је у томе што се овим алгоритмом не може претражити низ који није сотриран.

Функциналност алгоритма Уреди

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

Модификација алгоритама Уреди

Бинарно претраживање можемо модификовати тако да се уместо два идекса, користи само један индекс. Уместо горње и доње границе можемо рачунати средину и полупречник дела низа по коме претражујемо. Овако изгледа имплементација у програмском језику С.^[1]

int binarna_pretraga (int na, int trazenielement, int a[]) {
    int sredina, precnik;
    sredina = (na-1)/2; precnik = an;

    do
    {
        precnik = precnik/2;
        if(a[sredina] == trazenielement) return(s);
        if(a[sredina] < trazenielement) sredina += (precnik+1)/2;
        else sredina -= (precnik+1)/2;
    } 
    while(p);

    return(-1);
}

Анализа алгоритма Уреди

За разлику од алгоритма линеарног претраживања који ради у сложености О(n), алгоритам бинарне претраге ради у времену О(logn). Алгоритам ради у овом времену О(logn) јер агоритам не претражује цео низ већ само део низа тј. одређену половину.

Примери Уреди

Претрага низа бројева

Нека је низ А: 1 3 4 6 8 9 11

Кључ: к=4

1. корак: Пронаћи средишњи елемент

s=6

4<6 → Опредељујемо се за леви подниз.

се за леви подниз.

2. корак: Проналазимо средишњи елемент у низу 1 3 4

s=3

4>3 → Опредељујемо се за десни подниз.

3. корак: Претражјемо низ у коме имамо само један члан

s=4

4=4 → Пронашли смо тражени елемент. Претрага је завршена.

Ово је пример Бинарне претраге. У свакој итерацији дужина низа се преполови. Дакле, укупан број итерација не може бити већи од log⁡n

Игра погађања замишљеног броја

Игра почиње тако што особа А замисли један цео број између 40 и 60 (на пример). Остале особе могу да погађају замишљени број тако што изговарају један од бројева из познатог интервала. Особа А даје један од одговора: „Мањи“, „Већи“, „Тачан“. Уколико је особа А замислила број 44. Идеално би било да једна од особа која покуша са бројем 50, на шта би добила одговор „Мањи“, затим би следећи покушај био 45, а уследио би одговор „Мањи“. Претрага је сада смањена на свега 5 бројева. Следећи покушај би био 43, а одговор „Већи“. Особа која би поставила наредно питање, ако примењеје алгоритам бинарне претраге би погодила број 44. Алгоритам може радити и за негативне бројеве, на потпуно исти начин.

Телефонски именик

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

Референце Уреди

^ ^а ^б ^в Шкарић 2009, стр. 205
^ ^а ^б ^в Томашевић 2008, стр. 406

Литература Уреди

Томашевић, Мило (2008). „1”. Алгоритми и структуре података (1st изд.). Београд: Академска мисао. стр. 406. ISBN 978-86-7466-328--8. Приступљено 09. 02. 2016. „Сложеност алгоритама”
Шкарић, Милан; Виктор, Радовић (2009). „5”. Увод у програмирање (прво изд.). Београд: Микро књига. стр. 205. ISBN 978-86-7555-349-6. Приступљено 09. 02. 2016. „Претрага низа”
Introductions to algorithms -Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, књигу можете погледати овде Архивирано на сајту Wayback Machine (18. октобар 2016)
Алгоритми и структуре података - Мило Томашевић
Увод у програмирање - Милан Шкарић
Alexandrescu, Andrei (2010). The D Programming Language. Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-63536-5.
Bentley, Jon (2000) [1986]. Programming Pearls (2nd изд.). Addison-Wesley. ISBN 978-0-201-65788-3.
Chang, Shi-Kuo (2003). Data Structures and Algorithms. Software Engineering and Knowledge Engineering. 13. Singapore: World Scientific. ISBN 978-981-238-348-8.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd изд.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
Fitzgerald, Michael (2007). Ruby Pocket Reference. Sebastopol, CA: O'Reilly Media. ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A Practical Guide to Data Structures and Algorithms using Java. Boca Raton: CRC Press. ISBN 978-1-58488-455-2.
Leiss, Ernst (2007). A Programmer's Companion to Algorithm Analysis. Boca Raton, FL: CRC Press. ISBN 978-1-58488-673-0.
Moffat, Alistair; Turpin, Andrew (2002). Compression and Coding Algorithms. Hamburg, Germany: Kluwer Academic Publishers. ISBN 978-0-7923-7668-2. doi:10.1007/978-1-4615-0935-6.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th изд.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-57351-3.
Stroustrup, Bjarne (2013). The C++ Programming Language (4th изд.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2.

Спољашње везе Уреди

[Низ-1] а ^б ^в Шкарић 2009, стр. 205

[Комплексност-2] а ^б ^в Томашевић 2008, стр. 406

[1]

[2]

Бинарно петраживачки низ
Класа	Алгоритам сортирања^[1]
Структура података	Низ^[1]
Најгора перформанца	$O(logn)$ ^[2]
Најбоља перформанца	$O(logn)$ ^[2]
Најгора просторна комплексност	$O(n)$ ^[2]