>> РОБ БОВДЕН: Здраво, ја сам Роб.
Како запослити бинарну претрагу?
Хајде да сазнамо.
Дакле, имајте на уму да је ово претрагу идемо да спроведе рекурзивно.
Такође може да спроведе бинарну претрагу итеративно, па ако си то урадио,
то је савршено у реду.
>> Сада прво, хајде да се сетим шта параметри за претрагу требало да буде.
Ево, видимо инт вредност, што је требало да буде вредност је корисник
у потрази за.
Ми видимо инт вредности низ, који је низ у коме смо
у потрази за вредношћу.
И видимо инт н, који је дужина нашег низа.
>> Сада, прва ствар прво.
Ми проверите да ли н једнако 0, у ком случају се вратимо лажна.
То је само кажем ако имамо празан низ, вредност очигледно није у
празан низ, тако да може да се врати лажна.
>> Сада, ми заправо желимо да урадимо бинарне претраживање део бинарног претраживања.
Дакле, желимо да нађемо средину елемент овог низа.
Ево, ми кажемо средњи једнак н подељен са 2, јер средњи елемент је
ће бити дужина наш низ подељен са 2.
Сада ћемо да проверите да ли средњи елемент једнак вредности смо ми
у потрази за.
Дакле, ако вредности средње једнака вредности, ми смо могу да се врате тачно, јер смо
вредност у нашем низу.
>> Али, ако то није истина, сада морамо да урадимо Рекурзив
корак бинарног претраживања.
Ми треба да тражи или да лево од низа или
средини низа.
Дакле овде, ми кажемо да ли вредности на средини је мање од вредности, то значи да је вредност
била већа од средини од низа.
Дакле, вредност мора бити са десне стране елемент који смо управо гледали.
>> Дакле овде, идемо на Претраживач рекурзивно.
И ми ћемо погледати шта смо, пролазећи да то у секунду.
Али, ми ћемо да тражи да Право средњег елемента.
А у другом случају, то значи да вредност је мања од средине
низ, па идемо да тражи на лево.
Сада, лево ће бити мало лакше да погледате.
Дакле, овде видимо да смо ми рекурзивно позивајући претрагу где први
Аргумент је, опет, вредност гледамо преко.
Други аргумент ће бити низ који смо у потрази преко.
И последњи елемент сада је средњи.
Запамтите последњи параметар је наш инт н, тако да је дужина нашег низа.
>> У позиву рекурзивне поиска, ми смо Сада каже да је дужина
низ је средњи.
Дакле, ако је наш низ био величине 20 и ми претресли на индекс 10, пошто је средњи
20 подељено са 2, то значи да смо пролази 10 као нова
дужина нашег низа.
Запамтите да када имате низ дужине 10, то значи да важи
елементи су у индексима 0 до 9.
Дакле, то је управо оно што ми желимо да прецизира наш ажурирани Арраи - леви
арраи из средњег елемента.
>> Дакле, гледајући са десне стране је мало теже.
Сада прво, размотримо дужину од низа десно од
средњи елемент.
Дакле, ако је наш низ био од величине н, онда нови низ ће бити од величине н минус
средњи минус 1.
Дакле, хајде да мислимо о н минус средину.
>> Опет, уколико низ је величине 20 и делимо са 2 да се у средину,
па средњи је 10, онда н минус средњи ће нам дати 10, тако да је 10
елементи са десне средини.
Али ми такође имамо овај минус 1, јер не желимо да
обухватају саму средину.
Дакле н минус средњи минус 1 нам даје укупан број елемената на десној
средњег индекса у низу.
>> Сада овде, сећам се да је средњи параметар је низ вредности.
Дакле овде, ми пролази ажурира вредности низа.
Овај вредности плус средњи плус 1 је заправо говорећи рекурзивно позове
претраживање, пролази у новом низу, где да нови низ почиње у средини
плус један од наших првобитне вредности низа.
>> Алтернативни синтакса за то, сада то Ви сте почели да видите показиваче, је
амперсанд вредности средњи плус 1.
Дакле, зграбите адресу средину плус један елемент вредности.
>> Сада, ако нисте били пријатно допунама низ тако, ви
такође може да спроводи ово користећи рекурзивни функција помагач, где
да помагач функција узима више аргумената.
Дакле, уместо да само вредност, низ, а величина низа,
помагач функција могла узети више аргументи, укључујући нижи индекс
да би сте је стало у низу а горњи индекс да ти је стало
о низу.
>> И тако праћење и ниже индекс и индекс горњи, ви не урадите
Потребно је да измените икада оригиналне вредности низа.
Можете само да настави да користите вредности низа.
Али овде, приметите нам не треба помоћника функционишу док смо
спреман да модификује оригинал вредности низа.
Ми смо спремни да прође у Ажурирани вредности.
>> Сада, не можемо бинарну претрагу над низ који је некласификовани.
Дакле, хајде да то реши.
Сада, приметити да је врста прошлост два параметри инт вредности, која је
низ који смо сортирање, и инт н, која је дужина низа који
смо сортирање.
Дакле, овде желимо да спроведе алгоритам за сортирање
који је О н квадрат.
Можете да изаберете мехур сорт, избор врста, или уметање врста, или
нека друга врста нисмо види у класи.
Али овде, идемо на користи за избор врсте.
>> Дакле, идемо да вршите итерацију преко целог низа.
Па, овде видимо да смо итератинг од 0 до н минус 1.
Зашто не скроз до н?
Па, ако смо већ сортирани први н минус 1 елемената, затим
Веома последњи елемент који већ мора бити на правом месту, па преко сортирање
цео низ.
>> Сада, се како селекција Сортирај дела.
Идемо да иде преко целог низа у потрази за минималне вредности у
низа и штап који на почетку.
Онда ћемо да идемо преко целокупну Низ поново у потрази за другом
Најмањи елемент, а штап који у другом положају у
арраи, и тако даље.
Дакле, то је оно што овај ради.
>> Ево, ми смо видели да смо подешавање тренутног минимума
вредност на и-тој индекса.
Дакле, на првој итерацији, идемо да размотри минимална вредност буде
почетак нашег низа.
Онда, идемо да вршите итерацију над Остатак низа, провере да
видите да ли постоје неки елементи мањи од онај који ми тренутно смо
с обзиром на минимум.
>> Дакле овде, ј вредности плус један - то је мање него што смо тренутно
с обзиром на минимум.
Онда ћемо ажурирати шта ми мислимо да је минимална за
индекс ј плус 1.
Дакле, урадите то преко целог низа, и после тога за петље, минимум
треба да буде минимум елемент из и-ти положај у низу.
>> Када смо то, можемо да заменимо минимална вредност у и-тој позицији
у низу.
Дакле, ово је само стандардни своп.
Чувамо у привременом вредности - и-ти вредност у низу -
ставити у и-тој вредности у низу минимална вредност која припада тамо,
а потом складишти у назад где Тренутна минимална вредност некада
и-ти вредност у низу, тако да нисмо га изгубити.
>> Дакле, да се наставља на следећи итерација.
Ми ћемо почети у потрази за другом Минимална вредност и убаците да у
Друга позиција.
На трећем итерације, ми ћемо тражити вредност трећи минимална и убаци
то у трећој позицији, и тако све док имамо поређано низ.
Моје име је Роб, и то био избор врста.