[Музички] 

Даг LLOYD: Во ред. Па бинарни пребарување е алгоритам може да се користат да се најде на елемент во внатрешноста на низа. За разлика од линеарно пребарување, тоа бара посебен услов да бидат исполнети претходно, но тоа е многу поефикасна ако таа состојба се, всушност, се исполнети. 

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

Ако тоа е комплетна измеша, Ние не само да излезат од контрола отфрлите половина од елементите, бидејќи не се знае она што го отфрла. Но, ако низата е сортирана, ние може да го направи тоа, затоа што ние знае дека сè до лево од каде што ние сме во моментов мора да биде помал од вредноста ние сме во моментов во. И се што е на десно од каде сме мора да биде поголема од вредноста ние сме во моментов во потрага по. 

Значи она што е pseudocode чекори за бинарни пребарување? Се повторува овој процес додека низа или, како ние да продолжи во текот, под низи, помали парчиња оригиналната низа, е со големина 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 е она што го барате? Бр Тоа е прилично блиску, но ние сме во потрага по цена малку поголеми од тоа. 

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

Значи, да се земе многу помалку чекори од линеарно пребарување. Во најлош случај, имавме да се подели до листа на n елементи во неколку наврати во половина до својата цел, или поради тоа што цел елемент ќе биде некаде во последните поделба, или тоа не постои. Така што во најлош случај, ние треба да се подели на array-- знаеш? Дневник на n пати; ние мора да го намали проблемот половина на одреден број на пати. Дека бројот на пати се најавите n. 

Што е најдоброто сценарио? Па, кога првпат се пресмета средната точка, ние се најде она што го барате. Во сите претходни примери на бинарни пребарување ние сме само нема повеќе, ако имавме биле во потрага за елементот 15, ние би откриле дека веднаш. Тоа беше уште на самиот почеток. Тоа беше на средина на првиот обид за поделба на поделба во бинарна пребарување. 

И така во најлош случај, бинарни пребарување тече во дневникот n, што е значително подобро од линеарно пребарување, во најлош случај. Во најдобар случај, бинарни пребарување трча со омега на 1. Па бинарни пребарување е многу подобра од линеарно пребарување, но ќе мора да се справи со процесот на Сортирање вашето низа прво, пред да може да се искористување на моќта на бинарни пребарување. 

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