[За възпроизвеждане на музика] 

Дъг LLOYD: Добре. Така двоично търсене е алгоритъм можем да използваме да се намери един елемент вътре в масив. За разлика от линейната търсене, тя изисква специално условие бъде изпълнено предварително, но това е толкова много по-ефективна, това условие е, всъщност, се срещнаха. 

И така, какво е идеята тук? това е разделяй и владей. Ние искаме да се намали размера на зоната на търсене, като половината всеки път за да намерите мишена номер. Това е мястото, където това условие влезе в игра, все пак. Ние можем да използваме само силата на премахване на половината от елементите без дори да гледа тях, ако масивът е сортиран. 

Ако това е пълен микс нагоре, ние не можем просто от ръката изхвърли половината от елементи, защото ние не знаем какво се изхвърля. Но ако масивът е сортиран, можем да направим това, защото ние знам, че всичко, до останало от къде сме в момента са трябва да бъде по-ниска от стойност сме в момента. И всичко до право на къде сме трябва да бъде по-голяма от стойността ние сме в момента гледа. 

Така че това, което е Псевдокод стъпки за двоично търсене? Повтаряме този процес, докато масив или, докато напредваме през, под масиви, по-малки парченца оригиналния масив, е с размер 0. Изчислява се средната точка на текущата под масива. 

Ако стойността, което търсите е в този елемент на масива, спрете. Можете да го намери. Това е прекрасно. В противен случай, ако целта е по-малко от това, което е в средата, така че, ако стойността, което търсим е по-ниско от това, което виждаме, този процес се повтаря отново, но промяна на крайната точка, вместо е на оригинала завършат пълния спектър, да бъде само на ляво на мястото, където ние просто погледна. 

Знаехме, че средата е твърде висока, или целта е по-малко от средата, и затова трябва да съществува, ако изобщо съществува в масива, някъде в ляво от средата. И така, ние ще зададете на масива населено място само на ляво на средата като новия крайната точка. Обратно, ако целта е по-голямо от това, което е в средата, ние правим точно същото процес, но вместо това ние промяна на началната точка да бъде само за правото на средата ние просто изчислява. И след това, ние започваме процеса отново. 

Нека да визуализираме това, OK? Така че има много неща се случват и тук, но тук е масив от 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 там. Това е само, когато те преминават, че можем гарантира, че елементът не съществува в масива. 

Така че нека да се вземат много по-малко стъпки, отколкото линейно търсене. В най-лошия случай, имахме да се раздели на списък на наш елементи многократно в половината да намери целта, или защото целевата елемент ще бъде някъде в последното разделение, или тя не съществува изобщо. Така че в най-лошия случай, ние трябва да разделена на array-- знаеш? Вход на п пъти; ние трябва да намалят проблема наполовина определен брой пъти. Това няколко пъти е дневник п. 

Какво е най-добрия случай? Е, първият път, когато изчисляване на средната точка, ние намираме това, което търсите. При всички предишни примери за търсене в едномерен Току-що преминахме, ако имахме търси за елемента 15, щяхме да установи, че веднага. Това беше в самото начало. Това беше средата на първият опит за разцепление на разделянето в двоично търсене. 

И така, в най-лошите случай, двоичен търсене спринта Вход N, който е по същество по-добре отколкото линейно търсене, в най-лошия случай. В най-добрия случай, двоичен Търсене в спринта на омега на 1. Така двоично търсене е много по-добре от линеен търсене, но трябва да се справят с процеса на сортиране вашия масив първо, преди да можете да усетят мощността на двоично търсене. 

Аз съм Дъг Лойд. Това е CS 50.