Напредак се не прати јер нисте улоговани.
Садржај

Шта је бинарна претрага

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


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

Четири покушаја су увек довољна. Да ли сте успели да откријете како треба играти да бисте из највише 4 погађања открили замишљени број?

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

сумњиви бројеви:  [1   2   3   4   5   6   7   8   9   10  11  12  13  14  15]
покушај 1:                                     8
                                              / \
сумњиви бројеви:  [1   2   3   4   5   6   7]     [9   10  11  12  13  14  15]
покушај 2:                     4                               12
                              / \                             /  \
сумњиви бројеви:  [1   2   3]     [5   6   7]     [9   10  11]    [13  14  15]
покушај 3:             2               6               10              14
                      / \             / \             /  \            /  \
сумњиви бројеви:  [1]     [3]     [5]     [7]     [9]     [11]    [13]    [15]
покушај 4:         1       3       5       7       9       11      13      15

Колико покушаја би било потребно ако програм замишља број

  • од 1 до 7?

  • од 1 до 63?

  • од 1 до 1023?

  • Ако програм замишља број од 1 до 7, довољна су 3 покушаја.

  • Ако програм замишља број од 1 до 63, довољно је 6 покушаја.

  • Ако програм замишља број од 1 до 1023, довољно је 10 покушаја.

Можемо да приметимо да се број потребних покушаја повећава веома споро. То је зато што број сумњивих бројева у сваком покушају погађања може да се приближно преполови. Због тога од \(2^n- 1\) сумњивих бројева тражени број може да се погоди и у само \(n\) покушаја. На пример:

Број покушаја у зависности од величине скупа из ког се погађа

Величина скупа из ког се бира број

Довољан број покушаја

\(10~000 < 2^{14}\)

14

\(100~000 < 2^{17}\)

17

\(1~000~000 < 2^{20}\)

20

\(1~000~000~000 < 2^{30}\)

30

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

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

У Пајтону постоје две готове функције које спроводе поступак бинарне претраге. Да бисмо могли да их користимо, потребно је да на почетку програма напишемо import bisect.

  • Функција bisect.bisect_left(a, x) нам даје прву позицију у листи a на којој је елемент већи или једнак x. Ако таквог елемента нема, функција враћа дужину листе.

  • Функција bisect.bisect_right(a, x) нам даје прву позицију у листи a на којој је елемент већи од x. Ако таквог елемента нема, функција враћа дужину листе.

Показаћемо на неколико примера како се користе ове две функције.

Примери

Пример - да ли је број у листи

Пример - да ли је број у листи: У започетом програму дата је неопадајуће уређена листа бројева a, након чега програм учитава број x. Довршити програм, тако да исписује да ли се учитани број налази у листи. Ако је одговор потврдан, програм треба да испише и једну позицију на којој се учитани број налази.

Користићемо функцију bisect_left, јер она управо враћа прву позицију траженог елемента, ако он постоји.

Овде је било потребно да се поведе рачуна о једном детаљу: не треба писати a[bisect.bisect_left(a, x)], јер то може да доведе до пуцања програма у случају да функција bisect_left врати дужину листе.

Пример - мањи, већи, једнаки

Пример - број мањих, једнаких и већих елемената: У започетом програму дата је неопадајуће уређена листа бројева a, након чега програм учитава број x. Довршити програм, тако да исписује следеће податке:

  • колико елемената листе a је мање од броја x;

  • колико елемената листе a је једнако броју x;

  • колико елемената листе a је веће од броја x;

Према опису функције bisect_left можемо да закључимо да су од позиције коју нам она врати на даље сви бројеви већи или једнаки x (ако постоје), а на претходним позицијама су мањи бројеви (ако постоје). Према томе, ако та функција врати вредност L, тада су сви бројеви који су мањи од x на позицијама 0, 1, 2, ... L-1 и има их L.

Према опису функције bisect_right можемо да закључимо да су од позиције коју нам она врати на даље сви бројеви већи од x (ако постоје), а на претходним позицијама су мањи или једнаки бројеви (ако постоје). Према томе, ако та функција врати вредност R, тада су сви бројеви који су већи од x на позицијама R, R+1, ... N-1 и има их N-R (са N је означена дужина листе).

Из претходно реченог следи и да је број елемената листе који су мањи или једнаки x једнак R. Број елемената једнаких са x добијамо када од броја мањих или једнаких одузмемо број мањих. Дакле, број елемената једнаких са x је R-L.

На основу ове дискусије можемо да напишемо програм:

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

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

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

Задаци

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

Први јединствен елемент

Први јединствен елемент: Дати програм учитава листу a, а затим прави нову листу b, која садржи исте елементе, али уређене неопадајуће.

Довршити програм, тако да за сваки елемент листе a, бинарном претрагом листе b проверава да ли је тај елемент јединствен у листи, док не нађе један елемент који јесте јединствен.

Програм на крају исписује први јединствени елемент на који наиђе у листи a, или поруку да таквог елемента нема.

Пример 1: ако се по покретању програма унесе

5
1 4 1 5 2

програм треба да испише

4

Пример 2: ако се по покретању програма унесе

5
1 4 1 5 4

програм треба да испише

5

Пример 2: ако се по покретању програма унесе

6
1 4 1 5 4 5

програм треба да испише

nema

Брана

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

Живота жели да за сваки могући ниво воде одреди колико би улаза у склоништа остало на сувом (те улазе би требало затрпати). Улаз је на сувом ако је његова висина строго већа од нивоа воде.

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

Довршити програм, тако да за сваки ниво воде бинарном претрагом израчунава колико улаза би остало изнад тог нивоа воде.

Пример: ако се по покретању програма унесе

8
111 103 97 97 97 84 84 62
5
97 84 115 77 50

програм треба да испише

2 5 0 7 8

Оцене на контролном

Оцене на контролном: На контролном задатку може да се освоји од 0 до 100 поена. Задатак се оцењује на следећи начин:

  • од 0 до 40 поена - јединица;

  • од 41 до 55 поена - двојка;

  • од 56 до 70 поена - тројка;

  • од 71 до 85 поена - четворка;

  • од 86 до 100 поена - петица.

Ученици који су решавали задатак, освојили су редом 41, 76, 23, 85, 40, 0, 56, 66, 94, 70 и 100 поена. Довршити програм тако да помоћу бинарне претраге одређује оцену за сваког од њих.

Тема

Prijavi problem

Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.