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

Из Википедије, слободне енциклопедије

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

Бинарна претрага је дихотомни, „подели па владај“ претраживачки алгоритам.

Сажетак[уреди]

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

Увод[уреди]

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

Примери[уреди]

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


Нека је низ А: 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. Алгоритам може радити и за негативне бројеве, на потпуно исти начин.


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

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

Алгоритми[уреди]

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

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


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;

}

Перформансе[уреди]

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

Спољашње везе[уреди]