ROB BOWDEN: Прывітанне, я Роб. Як мы выкарыстоўваем бінарны пошук? Давайце высвятлім. Так, звярніце ўвагу, што гэты пошук мы збіраемся рэалізаваць рэкурсіўна. Акрамя таго, можна рэалізаваць бінарны пошук шматкроць, так што калі вы гэта зрабілі, гэта цалкам нармальна. 

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

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

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

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

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

У рэкурсіўнага выкліку для пошуку, мы цяпер кажуць, што даўжыня масіў сярэдні. Так што, калі наш масіў быў памерам 20 і мы Пошук па індэксе 10, так як сярэдзіна 20 падзяліць на 2, што азначае, што мы праходзячы 10 як новы даўжыня нашага масіва. Памятаеце, што калі ў вас ёсць масіў даўжынёй 10, гэта азначае, што дзейнічае элементы знаходзяцца ў індэксаў ад 0 да 9. Так што гэта менавіта тое, што мы хочам паказаць наш абноўлены масіў - левы Масіў з сярэдняга элемента. 

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

Зноў жа, калі масіў былі памерам 20 і мы дзелім на 2, каб атрымаць сярэдзіну, так сярэдзіна 10, то п мінус сярэдняга збіраецца даць нам 10, дык 10 элементы справа ад сярэдзіны. Але ў нас ёсць гэты мінус 1, так як мы не хочам, каб ўключаюць саму сярэдзіну. Так н мінус сярэдні мінус 1 дае нам Агульная колькасць элементаў справа сярэдняга індэкса ў масіве. 

Цяпер вось, памятаеце, што сярэдні параметрам з'яўляецца масіў значэнняў. Дык вось, мы перадаем абнаўленне значэнні масіва. Гэтыя значэння плюс сярэдні плюс 1 з'яўляецца фактычна кажучы рэкурсіўны выклік Пошук, пераходзячы ў новы масіў, дзе што новы масіў пачынаецца ў сярэдзіне плюс адзін з нашых першапачатковых значэнняў масіва. 

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

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

І так адсочвання і ніжняя індэкс і верхні індэкс, вы не трэба пастаянна змяняць зыходныя значэнні масіва. Вы можаце проста працягваць выкарыстоўваць масіў значэнняў. Але вось, звярніце ўвагу, мы не маем патрэбу ў памочніка функцыянаваць да тых часоў, як мы гатовыя змяніць арыгінал значэнні масіва. Мы гатовыя перадаць у Абноўлены значэння. 

Зараз, мы не можам бінарны пошук па масіў, які з'яўляецца малокомплектных. Такім чынам, давайце атрымаць гэтую разабрацца. Цяпер, звярніце ўвагу, што сартаванне апошнія два параметры дзесятковага значэння, якое з'яўляецца Масіў, мы сартаванне і Int N, што даўжыня масіва, мы сартавання. Такім чынам, вось мы хочам рэалізаваць алгарытм сартавання што ёсць пра н у квадраце. Вы можаце выбраць бурбалка сартавання, адбору сартаваць, або сартаванне ўстаўкамі, або некаторы іншы выгляд у нас не бачыў у класе. Але тут, мы збіраемся выкарыстоўваць выбару роду. 

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

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

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

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

Як толькі ў нас ёсць, што мы можам памяняць Мінімальнае значэнне ў г-й пазіцыі ў масіве. Так што гэта ўсяго толькі стандартны swap. Мы захоўваем у часовым значэнні - значэнне я-я ў масіве - значэнне змяшчаецца г-й у масіве Мінімальнае значэнне, якое належыць там, а затым захаваць назад у дзе току мінімальнае значэнне раней I-й значэнне ў масіве, так што мы не страцілі яго. 

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