[Мусиц плаиинг] 

Даг Ллоид: У реду. Дакле, бинарна претрага је алгоритам можемо користити да пронађе елемент унутар низа. За разлику од линеарне претраге, захтијева посебан услов да се претходно састали, али тако је много ефикасније да тај услов је, у ствари, срео. 

Дакле, шта је ту је идеја? то је завади па владај. Желимо да се смањи величину потрага простор за пола сваки пут како би се пронашли број одредишта. Ово је где је то услов долази до изражаја, ипак. Можемо само да искористе моћ елиминисања половина елемената без да гледа их ако је низ сортира. 

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

Дакле, шта је Псеудокод кораци за бинарни потрази? Понављамо овај процес док се низ или како да наставимо путем, суб низови, мањи комади оригинални низ, је величине 0. Израчунајте средиште тренутне под низа. 

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

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

Хајде да визуализују, ОК? Дакле, постоји много дешава и овде, али овде је низ од 15 елемената. И ми ћемо бити праћење а много више ствари овај пут. Дакле, у линеарном потрази смо били само брину о мету. Али овај пут желимо да брига где смо ми почиње да види гдје, стајемо у потрази, и шта је средиште тренутне низа. Дакле, идемо са бинарном претрагу. Ми смо прилично добро да иде, зар не? Само ћу да спустим испод овде скуп индекса. Ово је у суштини само оно што елемената од низа говоримо о. Са линеарном потрази смо брига, пошто смо ми Морам да знам колико Елементи смо итератинг преко, али не заправо брига шта елеменат тренутно гледамо. У бинарном претрагом, знамо. И тако они су само тамо као мали водич. 

Дакле, можемо да почнемо, зар не? Па, не баш. Запамтите шта сам рекао о бинарном сеарцх? Не можемо то урадити по принципу мусиц низ иначе, ми не гарантује да је извесни елементи или вредности нису као случајно одбачена када смо одлучи да игнорише половини низа. 

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

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

Тако смо укупну средиште по додајући 0 плус 14 подељено са 2; прилично јасно средину. И можемо рећи да средину је сада 7. Тако је 15 оно што тражите? Не то није. Тражимо 19. Али ми знамо да 19 је већа него што смо нашли на средини. 

Дакле, шта можемо да урадимо је промените почетну тачку да буде само на десно од средину, и поновите поступак поново. И када то урадимо, ми сада рећи Нови почетак Поента је низ локација 8. Оно што смо урадили је ефикасно игнорисао све са леве стране 15. Уклонили смо пола проблема, а сада, уместо да претражујете преко 15 елемената у нашем низу, имамо само да потражите преко 7. Тако 8 је нова почетна тачка. 14 је и даље крајња тачка. 

А сада, идемо кроз ово поново. Рачунамо нови средиште. 8, плус 14 је 22, подељено са 2 је 11. Да ли је то оно што тражите? Не то није. Тражимо вредности који је мање него што смо управо пронашли. Тако ћемо поновити Опет тај процес. Идемо да промените крајњу тачку на бити само са леве стране средње вредности. Дакле, нова крајња тачка постаје 10. И сада, то је само део Низ морамо да тражимо. Дакле, сада смо елиминисани 12 од 15 елемената. Знамо да ако 19 постоји у низу, да мора да постоји негде између елемента број 8 и елемент број 10. 

Тако да смо израчунали нове средиште поново. 8, плус 10 је 18, подељено са 2 је 9. И у овом случају, види, мета је на средини. Нашли смо управо оно што ми тражимо. Можемо зауставити. Ми успешно завршен бинарни претрага. У реду. Дакле, знамо овај алгоритам ради ако је мета негде унутар низа. Да ли овај алгоритам радити ако мета није у низу? Па, хајде да га покренете опет, и овај пут, Погледајмо за елемент 16, који визуелно можемо да видимо не нигде не постоји у низу. 

Почетна тачка је поново 0. Крајња тачка је опет 14. То су индекси првог и последњих елементи комплетног низа. И ми ћемо проћи кроз процес смо само прошао кроз поново покушавају да пронађу 16, иако визуелно, већ можемо рећи да неће бити тамо. Ми само желимо да се уверим да овај алгоритам ће, у ствари, још увек раде у неки начин и не само нас остави заглављен у бесконачну петљу. 

Дакле, шта је први корак? Израчунајте средиште тренутне низа. Шта је средину садашњег низа? Па, то је 7, зар не? 14 Плус 0 подељено са 2 је 7. Да ли је 15 оно што тражите? Ne. То је прилично близу, али ми тражимо за вредност незнатно већи од тога. 

Дакле, знамо да ће бити нигде са леве стране 15. Циљ је већи од оно што је у централном вредношћу. И тако смо поставили нову почетну тачку на бити само на десној страни средини. Средину је тренутно 7, тако Рецимо нови почетак поента је 8. И оно што сам ефективно опет урадио је игнорисао читава леви половини низа. 

Сада смо поновити обрађује још једном. Израчунајте нови средиште. 8, плус 14 је 22, подељено са 2 је 11. Да ли је 23 оно што тражите? Нажалост нема. Тражимо вредности то је мање од 23. И тако у овом случају, идемо да промените крајњу тачку да буде само лево од тренутног вредношћу. Тренутни мидпоинт је 11, и тако да ћемо поставити нову крајњу тачку за наредни пут кад одемо кроз овај процес до 10. 

Опет, идемо кроз процес поново. Израчунајте средиште. 8, плус 10 подељено са 2 је 9. Да ли је 19 оно што тражите? Нажалост нема. Још увек тражимо број мање од тога. Дакле, ми ћемо променити крајња тачка овог пута да буде само лево од средње вредности. Средину је тренутно 9, тако да крајња тачка ће бити 8. И сада, ми смо само тражимо при једној елемента низа. 

Шта је средиште овог низа? Па, почиње у 8, било завршава у 8, средиште је 8. Да ли је то оно што тражите? Да ли у потрази за 17? Не, ми тражимо 16. Дакле, ако постоји у низу, то мора да постоји негде на лево од места где тренутно смо. Па шта ћемо да радимо? Па, ми ћемо одредите крајњу тачку да буде само лево од тренутног вредношћу. Тако ћемо промијенити крајњу тачку до 7. Да ли видите шта се управо десило овде, иако? Погледајте овде сада. 

Старт је сада већи од краја. Ефикасно, два краја наше низа су прешли, и почетна тачка је сада након крајња тачка. Па, то не никаквог смисла, зар не? Дакле, сада, оно што могу да кажем је да имају под низ величине 0. А када смо стигли до ова тачка, сада можемо гарантује да елемент 16 не постоји у низу, јер почетне тачке и крајња тачка прешли. И тако да није ту. Сада, приметите да је ово благо разликује од почетне тачке и на крају Поента је иста. Да смо били у потрази за 17, она би морала био у низу, и почетне тачке и крајња тачка тог ласт итерација пре те тачке прешли, бисмо нашли 17 тамо. То је само када пређу да можемо гарантује да елемент не постоје у низу. 

Дакле, хајде да узмемо много мање кораци од линеарног потрази. У најгорем сценарију, имали смо да раздвојимо листу н елемената у више наврата на пола да пронађу циљ, или зато што је мета елемента ће бити негде у последња подела, или не постоји уопште. Дакле, у најгорем случају, морамо да разишли су арраи-- знаш? Се од н пута; ми морати да смање проблем за пола одређеном броју пута. Тај број пута је лог н. 

Шта је најбољи сценарио? Па, први пут смо израчунати средиште, нађемо оно што тражимо. У свим претходни примери бинарни потрази смо управо прошли кроз, ако смо имали Тражио елемента 15, бисмо открили да одмах. То је на самом почетку. То је био средиште први покушај делићу од поделе у бинарном потрази. 

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

Ја сам Доуг Лојд. Ово је ЦС 50.