[Гуляе музыка] 

Даг Lloyd: Добра. Так бінарны пошук з'яўляецца Алгарытм можна выкарыстоўваць знайсці элемент ўнутры масіва. У адрозненне ад лінейнага пошуку, ён патрабуе асаблівы стан быць выкананы загадзя, але гэта так значна больш эфектыўным, калі гэта ўмова, на самай справе, сустрэліся. 

Так што ідэя тут? гэта падзяляй і ўладар. Мы хочам, каб паменшыць памер вобласць пошуку на палову кожнага часу Каб знайсці нумар адрасата. Гэта дзе гэта ўмова уступае ў гульню, хоць. Мы можам толькі выкарыстаць магчымасці ухіляючы паловы элементаў нават не гледзячы на ім, калі масіў адсартаваны. 

Калі гэта поўная блытаніна, Мы не можам проста з рук адкінуць палову элементаў, так мы не ведаем, што мы адкідаючы. Але калі масіў адсартаваны, мы можам зрабіць гэта, таму што мы ведаць, што ўсё ў пакінулі, дзе мы ў цяперашні час павінна быць ніжэй, чым значэнне мы ў цяперашні час. І ўсё да Права, дзе мы павінна быць больш, чым значэнне мы ў цяперашні час глядзіць. 

Так што псевдокод крокі для бінарнага пошуку? Мы паўтараем гэты працэс да тых часоў, масіў або, як мы прайсці праз, суб масівы, дробныя кавалачкі зыходны масіў, мае памер 0. Разлічыць сярэднюю бягучага подобластей. 

Калі значэнне, якое вы шукаеце, у гэтым элеменце масіва, спыніцца. Вы яго знайшлі. Гэта выдатна. У адваротным выпадку, калі мэта менш, чым тое, што ў сярэдзіне, так што калі значэнне, якое мы шукаем для менш, чым тое, што мы бачым, паўтарыць гэты працэс яшчэ раз, але змяніць канчатковую кропку, а не быцця арыгінал завяршыць поўны спектр, каб быць толькі злева дзе мы проста глядзелі. 

Мы ведалі, што сярэдняя была занадта высокай, ці мэта была менш, чым у сярэдзіне, і таму ён павінен існаваць, калі ён наогул існуе ў масіве, дзе ў левай частцы сярэдзіны. І таму мы будзем ўсталёўваць масіў месца толькі для левай ад сярэдняй кропкі ў якасці новага канчатковага пункта. І наадварот, калі мэта больш, чым тое, што ў сярэдзіне, мы робім сапраўды такі ж працэс, але замест гэтага мы змяніць пачатковую кропку, каб быць толькі справа ад сярэдзіны мы толькі што вылічылі. І тады мы пачынаем працэс зноў. 

Давайце сабе гэта, добра? Такім чынам, ёсць шмат усяго адбываецца, і тут, але вось масіў з 15 элементаў. І мы збіраемся быць адсочванне шмат больш рэчаў на гэты раз. Такім чынам, у лінейным пошуку, мы былі толькі клапоцячыся пра мэту. Але ў гэты раз мы хочам, каб клапаціцца аб дзе мы пачынае выглядаць, дзе мы спыніліся, гледзячы, і тое, што сярэдзіна бягучага масіва. Дык вось мы ідзём з бінарнага пошуку. Мы даволі шмат добра ісці, праўда? Я проста хачу, каб пакласці ўніз ніжэй тут мноства індэксаў. Гэта ў асноўным толькі тое, што элемент масіва мы гаворым пра. Пры лінейным пошуку, мы клапаціцца, паколькі мы трэба ведаць, колькі элементы мы Перабор, але мы на самай справе не хвалюе, што элемент у цяперашні час мы глядзім. У бінарнага пошуку, мы робім. І так тыя проста там крыху кіраўніцтва. 

Такім чынам, мы можам пачаць, правільна? Ну, не зусім. Памятаеце, што я сказаў, аб двайковага пошуку? Мы не можам зрабіць гэта на малокомплектных масіў ці яшчэ, мы не гарантуе, што некаторыя элементы або значэння не выпадковага адкідаюцца, калі мы проста вырашылі ігнараваць палова масіва. 

Так крок адзін з бінарнага пошуку гэта вы павінны мець спарадкаваны масіў. І вы можаце выкарыстоўваць любы з сартавання алгарытмы мы гаварылі пра каб вы на гэтую пасаду. Так што цяпер, мы ў такім становішчы, калі мы можам выканаць бінарны пошук. 

Так давайце паўторым працэс крок за крокам, і трымаеце трэк, што адбываецца, як мы ідзем. Такім чынам, спачатку мы павінны зрабіць, гэта разлічыць сярэдзіна бягучага масіва. Ну, мы сказаць, што мы, у першую усе, гледзячы на ​​кошт 19. Мы спрабуем, каб знайсці нумар 19. Першы элемент гэтага Масіў размешчаны з індэксам нуль, а апошні элемент у гэтым Масіў размешчаны ў індэксе 14. І так мы будзем называць тых, пачатак і канец. 

Такім чынам, мы вылічыць сярэднюю па дадаўшы 0 ​​плюс 14 падзеленае на 2; даволі проста сярэдзіна. І мы можам сказаць, што сярэдзіна цяпер 7. Так 15 тое, што мы шукаем? Не, гэта не так. Мы шукаем 19. Але мы ведаем, што 19 больш, чым тое, што мы знайшлі ў сярэдзіне. 

Такім чынам, што мы можам зрабіць, гэта змяніць пачатковую кропку каб быць проста справа ад сярэдзіна, і паўтарыць працэс зноў. І калі мы гэта зробім, мы цяпер сказаць Новы старт кропка размяшчэння масіва 8. Тое, што мы зрабілі гэта эфектыўна ігнаруюцца ўсе злева ад 15. Мы ліквідавалі палову праблемы, і ў цяперашні час, замест таго, каб шукаць больш за 15 элементаў у масіве, у нас ёсць толькі для пошуку больш за 7. Так 8 з'яўляецца новы старт кропка. 14 па-ранейшаму з'яўляецца канчатковай кропкай. 

А цяпер, пяройдзем гэта зноў. Мы вылічаем новае сярэдзіну. 8 плюс 14 22, дзеліцца на 11 лютага. Гэта тое, што мы шукаем? Не, гэта не так. Мы шукаем значэнні, менш, чым тое, што мы толькі што знайшлі. Так што мы збіраемся паўтарыць працэс зноў. Мы збіраемся змяніць канчатковую кропку для як раз злева ад сярэдзіны. Такім чынам, новы канчатковы пункт становіцца 10. А цяпер, вось толькі частка масіў, мы павінны разабрацца ў. Такім чынам, мы ўжо ліквідаваны 12 з 15 элементаў. Мы ведаем, што, калі 19 існуе ў масіве, гэта павінен існаваць дзесьці паміж элементам № 8 і № 10 элемент. 

Такім чынам, мы вылічаем новае сярэдзіну зноў. 8 плюс 18 кастрычніка, дзеліцца на 9 лютага. І ў гэтым выпадку, глядзіце, мэта ў сярэдзіне. Мы знайшлі менавіта тое, што мы шукаем. Мы можам спыніць. Мы паспяхова завяршылі двайковы пошук. Добра. Такім чынам, мы ведаем гэты алгарытм працуе, калі мэта дзесьці ўсярэдзіне масіва. Ці азначае гэта працаваць, калі алгарытм мэта не ў масіве? Ну, давайце пачнем яе зноў, і на гэты раз, давайце паглядзім на элемент 16, якія візуальна відаць, нідзе не існуе ў масіве. 

Пачатковая кропка зноў 0. Канчатковая кропка зноў 14. Такія паказчыкі першага і Апошнія элементы масіва. Поўны І мы будзем ісці праз працэс мы толькі пайшоў праз раз, спрабуючы знайсці 16, нават калі візуальна, мы можам ужо сказаць, што ён не збіраецца быць там. Мы проста хочам, каб пераканацца, што гэты алгарытм будзе, на самай справе, да гэтага часу працуюць у нейкай меры і не проста пакінуць нам затрымаўся ў бясконцым цыкле. 

Так што крок першым? Разлічыць сярэднюю бягучага масіва. Што сярэдзіна бягучага масіва? Ну, гэта 7, праўда? 14 плюс 0 падзяліць на 2, 7. 15 тое, што мы шукаем? Няма. Гэта даволі блізка, але мы шукаем для значэння трохі больш, чым гэта. 

Такім чынам, мы ведаем, што гэта будзе ня быць нідзе злева 15. Мэтавае больш што ў сярэдзіне. І таму мы ўсталёўваем новую пачатковую кропку для як раз справа ад сярэдзіны. Сярэдзіна ў цяперашні час 7, так скажам, новую пачатковую кропку 8. І тое, што мы фактычна зрабіць яшчэ раз ігнаруецца уся левая палова масіва. 

Цяпер мы паўтараем апрацоўваць яшчэ раз. Разлічыць новую сярэднюю. 8 плюс 14 22, дзеліцца на 11 лютага. 23 тое, што мы шукаем? На жаль, няма. Мы шукаем значэнне што менш, чым 23. І таму ў дадзеным выпадку, мы збіраемся змяніць канчатковую кропку, каб быць проста злева ад бягучага сярэдзіне. У цяперашні час сярэдняя кропка 11, і таму мы задамо новую канчатковую кропку у наступны раз мы ідзем праз гэты працэс да 10. 

Зноў жа, мы ідзем праз працэс зноў. Разлічыць сярэднюю. 8 плюс 10 дзеліцца на верасень 2.. Ёсць 19, што мы шукаем? На жаль, няма. Мы ўсё яшчэ шукаем лік менш. Такім чынам, мы змяніць канчатковую кропку на гэты раз быць проста злева ад сярэдзіны. Сярэдзіна ў цяперашні час 9, так што канчатковая кропка будзе 8. І зараз, мы проста шукаем у адным масіве элемента. 

Што сярэдзіна гэтага масіва? Ну, ён пачынаецца ў 8, гэта заканчваецца ў 8, сярэдзіна 8. Гэта тое, што мы шукаем? Мы шукаем 17? Не, мы шукаем 16. Так што, калі ён існуе ў масіве, яна павінна недзе існаваць злева, дзе мы ў цяперашні час. Так што мы будзем рабіць? Ну, мы ўсталяваць канчатковую кропку, каб быць проста злева ад бягучага сярэдзіне. Такім чынам, мы змяніць канчатковую кропку да 7. Вы бачыце, што толькі тут адбылося, праўда? Паглядзіце тут. 

Пачаць зараз больш, чым канец. Фактычна, два канцы з нашага масіва перайшлі, і пачатковая кропка знаходзіцца Зараз пасля таго, як у канчатковай кропцы. Ну, гэта не ніякага сэнсу, ці не так? Так што цяпер, што мы можам сказаць, што мы ёсць суб масіў памерам 0. І як толькі мы дабраліся да Гэтая кропка гледжання, мы можам у цяперашні час гарантаваць, што элемент 16 не існуе ў масіве, таму пачатковай кропкі і канчатковая кропка перайшлі. І такім чынам гэта не там. Цяпер, звярніце ўвагу, што гэта крыху адрозніваецца ад пункту пачатку і заканчэння Сутнасць у тым, тое ж самае. Калі б мы былі гледзячы на 17, гэта было б быў у масіве, і кропкі старту і канчатковая кропка гэтага апошняй ітэрацыі перш чым гэтыя кропкі перасякаюцца, мы б знайшлі 17 там. Гэта толькі, калі яны перасякаюць, што мы можам гарантаваць, што элемент не існуе ў масіве. 

Такім чынам, давайце шмат менш крокаў, чым лінейны пошук. У горшым выпадку, мы мелі падзяліць спіс элементаў п неаднаразова ў палове, каб знайсці мэта, альбо таму, што мэтавай элемент будзе дзесьці ў апошні дзяленне, ці ён не існуе наогул. Такім чынам, у горшым выпадку, мы павінны падзяліць на array-- вы ведаеце? Часопіс п разоў; мы павінны скараціць праблемы у палове пэўную колькасць разоў. Гэта колькасць разоў з'яўляецца часопіс п. 

Які самы лепшы сцэнар? Ну, у першы раз мы разлічыць сярэднюю, мы знаходзім, што мы шукаем. Ва ўсіх папярэдніх прыклады на бінарны пошук мы толькі што скончылася, калі б мы мелі шукаў элемента 15, мы выявілі, што неадкладна. Гэта было ў самым пачатку. Гэта было сярэдзіна першая спроба расколу дывізіі ў бінарны пошук. 

І так у горшым так, бінарны пошук працуе у часопісе п, што значна лепш, чым лінейны пошук, у горшым выпадку. У лепшым выпадку, двайковы Пошук працуе амега 1. Так бінарны пошук шмат лепш, чым лінейны пошук, але вам даводзіцца мець справу з працэсам сартаванне свой масіў, перш чым вы можаце выкарыстоўваць сілу двайковага пошуку. 

Я Дуг Лойд. Гэта CS 50.