SPEAKER 1: Хей всички! Добре дошли отново в раздел. Толкова се радвам да видя толкова много от вас, както тук, и всеки, който гледа онлайн. Така че, както обикновено обратно дошли. Надявам се, че всички сте имали прекрасен уикенд, пълен с почивка, релаксация. Вчера беше красиво навън. Така че, надявам се да се радва на открито. 

Така че на първо няколко съобщения. Окачествяването. Така че, повечето от вас трябва да са придобили едно приятел от мен за вашата Scratch Pset, както и класификация за Pset 1. Така, само няколко неща. Не забравяйте да използвате check50 в style50. Те са предназначени да бъдат ресурси за вас, момчета, да се уверите, че сте се най-много точки, колкото можете без ненужно да ги губи. Така че, неща като стил са много важни. Ние ще да излети за него. Някои от вас може би вече Забелязах, че от вашия Pset. И check50 е просто наистина лесен начин да се уверите, че ние всъщност връщане какво трябва да бъдат върнати на потребителя, и че всичко работи правилно. 

На втората бележка, се уверете, че качване неща се до правилната папка. Това прави живота ми просто Малко по-трудно ако качите Pset 2 в Pset 1 защото когато изтегля неща, те не се изтегля, правилно. И аз знам, че е малко деформирани в системата, за да свикна, но просто е супер внимателни, дори и само за мен, така че, когато вие получавате имейли в като 2 часа сутринта и аз съм оценяване. Ако не е, защото аз трябва да гледам всичко около вашия Pset. Cool. 

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

Така че, проблема си зададете, номер три. Колко хора са чели спец от любопитство? OK. Имаме една двойка. Вид надолу от миналата седмица, но това е ОК. Знам, че беше красиво навън. Така Break Out. Определено, след като се направи днес четете спец поне опитайте като свалянето разпространение на кодове и бягане като първоначална нещо, което те ви помоля да. Тъй като ние сме с помощта разпределение код и библиотека че сме били само using-- --It само За втори път сме правили този Pset, луди неща могат да се случат с вашия уред, и искате да откриете, че сега в сравнение с по-късно. 

Защото, ако това е в четвъртък вечер или това е Сряда вечер и по някаква причина Вашият уред просто не прави искате да стартирате с библиотеката или с разпределението код, това означава, вие дори не може да започне да прави кодирането. Тъй като не може да се провери да видим дали тя работи. Вие не ще бъде в състояние за да видите дали той съставя. Искаш ли да се грижи за тези, които в началото седмицата, когато все още можете да се свържете с мен или някоя от другите TFS, и можем да получим тези фиксирани. Тъй като това са въпроси които се случва да ви спре от извършване на реален напредък. Това не е като един бъг, че може просто вид прескачам. Ако имате проблеми с вашия уред или разпространение на кодове, Наистина ли искате да се вземат, че грижи за по-рано, отколкото късно. Така че, дори ако не сте ще всъщност започнете кодиране, изтеглите разпределението код, прочетете спец, уверете се, всичко работи там. OK? Ако само можете да направите това, аз Обещавам живота ви ще бъде по-лесно. И така, вие вероятно ще да го направя точно сега, нали? OK. Така че, на всички въпроси там? Всички логистични неща? Всеки е добре? OK. 

Общи условия за тези от ви в стаята и онлайн. Отивам да се опитва да превключвате между PowerPoint в уреда защото ние ще да се правят някои кодиране днес от популярни търсенето на анонимните анкета предложение изпратих миналата седмица. Така че, ние ще се правят някои кодиране. Така че, ако вие също искат на огън на вашите уреди, и вие трябва да имам имейл от мен, с примерен файл. Моля, чувствайте се свободни да правят това. 

Така че, ние ще говорим за GDB, което е дебъгер. Това ще ви помогне вид разбера къде нещата са наред в кода си. Това е наистина само един начин да се засили чрез вашия код, както това се случва, и да бъде в състояние да отпечатате променливи или да видим какво всъщност се случва под капака стихове си програма само с тичане, това е като Faulting, и вие сте като няма представа какво точно се е случило тук. Аз не знам какъв ред се провали в. Аз не знам къде се обърка. Така че, GDB ще ви помогне с това. Също така, ако сте решили да продължи да, и да вземат 61, това ще е много, наистина да ви бъде най-добър приятел, защото аз мога да ви кажа защото аз ще съм през този клас. 

Отиваме да разгледаме двоичен търсене, което, ако вие не забравяйте великият пример на телефонния указател спектакъл от класа. Ние ще се прилагане на това, и разхождах из че малко повече, и след това отиваме през четири различни видове, които са Bubble, Подбор, вмъкване и Merge. Cool. Така че, GDB, както споменах, е дебъгер. И те са вид на големите неща, на големите функции или команди че можете да използвате в GDB, и аз ще ходя вас чрез демонстрация на това в секунда. 

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

Също така, ако имате някаква външна функционира като Swap или Cube, че ние погледна миналата седмица. Ако ви кажа, наруши една от тези, всеки път, когато програмата ви удари, че тя ще изчака, за да кажи какво да правя. Преди това само ще изпълнява, така че в действителност може да се оттегли във вътрешността на функцията и да видим какво се случва. Така че, Next, просто прескача Следващата линия, преминава функции. Стъпка. Те всички са малко абстрактно. Така че, аз съм просто ще да тече през тях, но вие ще ги видите в употреба в секунда. 

Стъпка в дадена функция. Така че, както казах, като с Swap, че ще ви позволи да всъщност, като че ли сте като физически засилване вътре, можете да се забъркваш с тези променливи, печат какви са те, да видим какво се случва. Списък буквално само ще отпечата от заобикалящата код. Така че, ако имате нещо да забравя когато сте във вашата програма, или се чудите това, което се случва около него, това просто ще отпечатате сегмент от искал пет или шест линии около него. Така че, можете да се ориентирате за това къде се намирате. 

Печат някои променлива. Така че, ако имате ключа като в Цезар, че ние ще разгледаме. Може да се каже Print Key във всеки един момент. Тя ще ви кажа каква е стойността е толкова че може би някъде по пътя, можете презаписано ключ. Всъщност можете да кажете, че тъй като всъщност може да се отбележи, че стойност. 

В местните жители, само отпечатъците вашите локални променливи. Така че, по всяко време, вие сте в една линия, и просто искате да видите като, о. Каква е моята ли? Каква е тази ключова ценност че аз се инициализира тук? Какво е посланието на този етап? Тя просто ще отпечата всички на тези, така че да не трябва да се индивидуално се каже, Print I. Print Message. Print Key. И тогава дисплея. Какво, че прави, е като ви стъпка чрез програмата, тя просто ще се уверите, че това е показване на някаква определена променлива във всеки един момент. Така че можете also-- --it е вид на пряк път, когато не е нужно да продължава напред, като, о. Print Key или Print I. Тя просто автоматично ще го направя за теб. 

Така че, с това, ние отиваме да видим как това отива. Отивам да се опита и да преминат на моя уред. Виж, ако мога да направя това. All. Ние просто ще го отразяват. Няма нищо по-луд на моя лаптоп все пак. OK. Това трябва да бъде тази. Тя е толкова малка. Да видим дали можем да направим това. 

OK. Алис е очевидно борейки тук само за малко, но ние ще го получите в Моменто. OK. Ние просто ще се увеличи тази. OK. Може ли всеки вид се види, че? Може би малко по-малко? Знам, че е малко по-малък. Вие не може съвсем да разбера как да се направи това по-голям. Ако някой знае. Някой знае ли как да се направи по-голям? OK. Отиваме да се търкаля с него. Няма значение, така или иначе, защото това е просто това е код, който вие трябва да имаме. 

Какво е по-важно е терминал тук. И ние имаме тук Защо е толкова малка? Настройки. О. True Айк. Как е това? От там. Това ли е по-добре за всички? OK ,. Cool. 

Знаеш ли, когато сте в CS технически трудности клас са вид на част от the-- Така че, нека да изчистите това. OK. Така че, точно тук, в раздел, което имахме тук. Цезар е изпълним файл. Така че го е направил. Така че, едно нещо, което да се реализира с GDB е че тя работи само на изпълними файлове. Така че, не можете да го стартирате по dotsy. Трябва наистина да се направи уверите, че вашият код компилира, и че тя действително може да се управлява. 

Така че, уверете се, че ако това не стане събират, за да го да се съберат, така че да можете да вид тече през него. Така че, за да стартирате GDB, всичко, което правим, Gloria тип GDB, и след това просто файла, който искате. Аз винаги misspell Цезар. Но вие искате да се уверите, тъй като това е един изпълним, точка флаш ти, така че означава, че започваш да тече CSI ти започваш да се изпълни това файлове или с дебъгер. OK. Така че, можете да направите това, можете да получите този вид безсмислици. Тя е само на всички неща за дебъгер. Вие наистина не трябва да се се тревожи за това точно сега. И както виждате, ние имаме това отворени parens БВП, близки parens, и просто вид прилича нашата командния ред, нали? 

Така че, това, което ние искаме да do-- --So, Първото нещо, е, че ние искаме да изберем място, където да го счупи. Така че, има един бъг в тази програма Caesar че аз се въведе, че отиваме, за да разберете. Това, което тя не е необходимо на входа Barfoo във всички капачки, и по някаква причина това не променя A. Тя просто напуска само тя, е всичко друго, правилно, но второто писмо А остава непроменена. Така че, ние ще се опитаме и разбера защо това е така. Така че, първо трябва нещо обикновено искате да направите, когато започне на GDB е да разбера къде да го счупят. 

Така че Цезар е доста кратка програма. Ние просто трябва една функция, нали? Каква е нашата функция в Цезар? Има само една функция, Главна нали? Main е функция за всички ваши програми. Ако не сте имали Main, бих могъл е малко притеснен в момента, но се надявам всичко, което трябваше Главна там. И така, какво можем да направим, е да можем да просто се счупи на Майн, просто ей така. Така че, той казва, OK. Ние поставяме нашата гранична стойност един там. 

Така че, сега нещо трябва да запомните е Caesar има една команда аргумент ред точно и ние не сме направили, че все още никъде. Така че, това, което правите е, когато всъщност отиде да работи програмата, всяка програма, която сте работи в GDB, че се нуждае от командния ред аргументи, започваш да въведете когато за първи път започнете да го използвате. Така че, в този случай, ние правим Стартирай с ключ на три. И това всъщност ще започне. 

Така че, ако ви видя тук, имаме Ако RC не е равно на две. Така че, ако вие, момчета, всички от които имат този файл, че аз изпратих до ще видите, че това е като първа линия нашата основна функция, нали? Това е проверка, за да видим дали имаме точния брой аргументи. Така че, ако се чудите ако RC е правилна, можете да направите нещо точно като Print RC. RC е две, което е това, което очаквахме, нали? 

Така че, можем да отидем Next, и да продължи сам. Така че, ние имаме някои ключови там. И ние можем да отпечатате нашия ключ да се уверите, че е правилно. Интересно. Не е точно това, което очаквахме. Така че, едно нещо, което да се реализира с GDB също е че това не е, докато вие всъщност удари На следващо място, че линията, която току-що видяхте всъщност е изпълнена. Така че, в този случай Key все още не е определен. Така че, Key е някаква ценност боклук който виждате на дъното там. Negative $ 120-- --It на един милиард И нещо странни неща, нали? Това не е ключът, който очаквахме. Но ако ние се удари Next, и след това ние опитайте и ключ за печат, това е три. 

Всеки вижда, че? Така че, ако се получи нещо че вие ​​сте като почака. Това е напълно погрешно, и аз не знам как това ще се случи, защото всичко, което искам да направите, е да зададете номер, променлива, опитайте удря След това опитайте печат отново, и да видим дали работи. Тъй като това е само ще се изпълни и всъщност възлага нещо, след като натиснете Next. Уверете се смисъл на всички? Ами нали? 

SPEAKER 2: Когато случайно номера какво означава това? 

SPEAKER 1: Това е просто случаен принцип. Това е просто боклук. Това е просто нещо, което си компютър на случаен принцип ще присвоите. Cool. Така че, сега ние можем да преминат през и т.н. сега имаме този текст GetString. Така че, нека просто да се въведе това, което ще се случи, когато се удари Next тук. Нашата GDB вид изчезва, нали? Това е така, защото GetString сега се изпълнява, нали? Така че, когато видяхме, обикновен текст се равнява GetString, отворени parens и parens, и ние удари Next, която има всъщност изпълнява сега. Така че, това е очакване ни за въвеждане на нещо. 

Така че, ние отиваме да въведете нашата храна, която е това, което е липса както ви казах и че просто се казва, че това е завършено изпълнение, че закрито скоба означава, че е излизане от тази линия. Така че, ние може да удари Next, и сега, когато съм че всички сте запознати от Цезар, това е, какво е тази линия ще направим. Това е за Int I е равна на 0, N е равно на Strlen, обикновен текст, а след това I е по-малко от N, I, плюс, плюс. Каква е тази линия ще правиш? Отворете съобщението. Cool. Така че, нека да започнем да правим това. 

Така че, в случай че това условие съвпадат, за първата ни един? Ако това е B, това е обикновен текст I. Ние може да получите информация за нашите местни жители. Така че, аз е нула, и ако е шест, което ние очакваме и нашата ключ е три. Всичко, което има смисъл, нали? Тези цифри са точно това, което трябва да бъде. Така че, си тананика? SPEAKER 3: Имам случайни числа за мината. SPEAKER 1: Е, ние можем да --we check-- да говорите за това в секунда. Но вие трябва да получавате това. Така че, ако имаме капитал B за първия ни един, това състояние трябва да го хване, нали? Така че, ако ние натиснете Next, ние виждаме, че този Ако действително изпълнява. Защото, ако сте след заедно в кода си, тази линия тук, където обикновен текст I се заменя с това аритметика, изпълнява само ако, ако състояние е правилно, нали? 

GDB само ще ви покажа неща, които в действителност оперират. Така че, ако това условие, ако не е изпълнено, това е просто ще преминете към следващия ред. OK? Така че, ние имаме това. Тази скоба означава, че е приключването на този цикъл сега. Така, че ще започне отново. Просто ей така. Така, че можем да получим информация за нашите местни жители тук, и ние виждаме, че първата ни писмо се е променило, нали? Това е сега Е, тъй като тя трябва да бъде. Така че, можем да продължим нататък. 

И ние имаме тази проверка. И тази проверка трябва да работи, нали? Това е А. Трябва да се промени три букви напред. Но ако забележите, ние се получи нещо по-различно. Така че в този случай тук, я хвана то, и така тази линия изпълнена, които модифициран нашия B. Но в този случай тук, имаме, че тя просто го прескочи, и отиде до [? L София Филм Фест. ?] Така че нещо се случва там. Какво, че ви казва, е, че ние знаем, че той трябва да хване тук, но това не е така. Може ли някой да видим какво ни Проблемът е в тази линия? Това е много минути нещо. И вие също може да погледнете кода си. Това е също така line-- забравя какво линия е в there-- но това е в [недоловим]. Да? 

SPEAKER 4: Това е по-голям от страница, ако сте го прочели в книгата. SPEAKER 1: Точно така. Така че, дебъгер не може да каже ви, но дебъгер може ли да попречи на линия че знаете, не функционира. И понякога, когато особено по-късно през семестъра, когато имаш работа със сто, а сто няколко реда код, а вие Не знам къде е липса, това е чудесен начин да го направя. Така че, ние открихме нашата грешка. Можете да го оправя във файла, и след това можете да го стартирате отново, и всичко ще работи перфектно. И най-голямото нещо, което е това може да изглежда като, OK. Да. Cool. Знаеш, че това, което търсите. Така че, знаех какво да правя. 

GDB може да бъде супер полезно, защото може да разпечатате всички тези неща, които ви не би. Това е много по-полезно, отколкото ФОРМАТ. Колко от вас използват като ФОРМАТ отчети да разбера къде е грешка беше, нали? Така че, с това, че не правим Трябва да продължаваме назад, и искал да коментира в ФОРМАТ или коментирате, и да разбера какво трябва да се печата. Това всъщност само ви позволява да стъпка през разпечатва неща като отиваш през, така, можете да се наблюдава как те се променят в реално време, като програмата се изпълнява. 

И тя не взема малко малко на привикване. Бих силно препоръчвам просто вид че е малко разочарован с него за сега. Ако прекарвате повече от час на Следващата седмица се научите как да използвате GDB, вие ще си спестите толкова много време по-късно. И буквално. разказваме това хора всяка година, и аз си спомням, когато взех клас, аз бях като, че ще се оправи. Не. Pset 6 дойде и аз бях като, аз ще научите как да се използва GDB, защото аз не правя знам какво става тук. 

Така че, ако имате време, така че го използвате за по-малки програми че ти започваш да бъде работа на открито, като работи чрез нещо като Visionare, като този. Или, ако искате допълнително практика, аз съм сигурен, че Аз може да излезе с бъги програми, за да можете да трасира ако искате. 

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

Така че, ако се върнем към нашата PowerPoint. Дали това ще се работи? AWH. Да. OK. Така че, ако някога ви се наложи някоя от тези, отново, там е в списъка. Така Binary Search, която всеки помни великия спектакъл на David извличане на телефонни указатели на половина. Аз наистина не получите телефонни книги вече, тъй като, когато се направи Вземи телефонни книги тези дни? Аз наистина не знам. The Binary търсене. Дали някой си спомня как Binary произведения търсене? Някой изобщо? Така ли? SPEAKER 5: Знаеш ли, когато погледнете коя половина би било в въз основа на това, и да се отървете от другата половина. 

SPEAKER 1 Точно така. Така че, Binary Search, това е вид на A-- --we искал да го наричат ​​разделяй и владей. Така че, това, което ще направим, е да вие ще погледнете в центъра, и ще видите, ако тя отговаря на това, което търсите. И ако това не стане, тогава ще се опитаме да разбера, е, че ще бъдат оставени половината или дясната половина. Така че, това може да бъде, ако търсите на нещо, което е по азбучен ред, виждате ли, о. Дали Allison дойде пред M? Да. Така че, ние ще Посетете първото полувреме. 

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

Така че, ние имаме N, което е линейно време. Ако N над две, което е малко по-добре, все още расте супер бързо. И тогава ние сме Влез, което е това, което ние считаме Binary Search. Ако забележите, като проблем получава много и много по-голям, времето, което ви е необходимо, за да го решим наистина не се увеличи толкова много. Това е като да сравним тук в началото. Вие сте като OK. Нещо тук не е така наистина въпрос, който един ние използваме, но можете да получите до един милион, милиард. Вие се опитвате да намерите some-- --you're се опитва да намери игла в купа сено. 

Мисля, че искате този проблем. Вие искате тази сложност, не линейна, защото за всички вас знаете ще се търсят чрез всяка отделна игла, нещо от сено, се опитва да търси иглата. И това не е твърде забавно, по мое мнение. Харесва ми бързо. Обичам ефективен. И като трудолюбиви студенти вас момчета са, знаете, работят умни, не по-трудно тип нещо, как сте може да компенсира тези алгоритми. 

Така че, ние ще ходим чрез само един бърз пример. Мисля, че вие, момчета, трябва да имат ръка на Binary Search, но в случай, че някой е малко по- размита, искам да го засили, отиваме просто да отида чрез пример тук. Така че, ние не търсим, ако масива съдържа седем. 

И така, първото нещо, което правим, е погледнете в центъра, нали? А също и ти започваш да се кодиране Binary Търсене само за секунда. Така че, това ще бъде забавно. Така че ние с нетърпение в средна малки масиви 3. Има 3 равни 7? Не. Това е шест. Значи, това е по-малко от или повече от седем? По-малко от. Да. Хубави момчета за работа. Аз чувствам, че искал аз трябва има бонбони, защото аз искам да го изхвърля в дворовете. Това е, което аз ще направя следващата седмица. Това ще ви предпази момчета остър. 

Така че, ние изхвърляме, че Първата половина, нали? е по-малко от. ние знаем, че всичко на този от лявата страна ще бъде по-малко от това, което ние всъщност търсите. Така че, няма нужда да обърне внимание на това. Просто забрави за това. Така че, сега се вгледаме в полето наша страна ръка, и ние с нетърпение в средата там, и сега е девет. Така че, 9 is-- --Everyone? По-голямо от това, което сме търсите, нали? Така че, ние отиваме да хвърлят далеч всичко надясно. Подобно на това. Сега, всички ние сме оставени с такава. Така че, ние проверяваме, е този какво ние, което търсите? е то. Намерихме това, което искахме. Така че сме готови. Bilinear Search. 

И ако забележите, ние имаше седем входа там. Отне ни само като три пъти, но ако правиш като един милиард, вие знаете колко стъпки тя би предприеме, ако имахме четири милиарда неща? Всякакви предположения? Това е 32. 32 стъпки, за да намерят нещо в четири милиарда масив, защото на правомощията на две. Така е две до 32, е четири милиарда. 

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

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

Така че, ако можете да разбера out-- имам намек there-- какви са случаите, това, което имаме тук? Така че, ако искате, за да разбера случаи, ние ще Псевдокод тези и тогава ние всъщност ще им код. И това ще бъде, аз мисля, да се надяваме, че ще е малко по-лесно, отколкото сте очаквали. Тъй като това не е толкова много код, всъщност, което е наистина страхотно. 

Мм-хм? 

STUDENT: [недоловим]? ИНСТРУКТОР: Да. Имаше нещо да се намери в средата. 

STUDENT: Така че ние можем да използваме това. OK. 

ИНСТРУКТОР: Perfect. Така че това е първото нещо, което трябва да направим. Така че намери средата. Страхотно. Така че, имате ли представа за това как бихме могли всъщност се намери средата с код? 

Студентът: Да. п над 2? ИНСТРУКТОР: Значи п над 2. Така че едно нещо, което трябва да запомните е, че вашите горни и долни граници се променят. Ние продължаваме да свива страна на масива, което търсим да. Така п над 2 ще работи само за първото нещо, което правим. Така че, като горната и долната предвид, как бихме могли да получите, че средната елемент? Тъй като ние искаме средата между горната и долната част, нали? Мм-хм? 

STUDENT: [недоловим]. 

ИНСТРУКТОР: Така че ние имаме някаква средна. И това ще бъде горната плюс ниска над 2. Awesome. Има отидем. Един ред надолу. Вие, момчета, сте на път. Така че сега ние имаме средна, какво искаме да направим? Просто като цяло. Не е нужно да го кодират. Да. STUDENT: [недоловим]? ИНСТРУКТОР: Така че това е плюс, защото сте намирането на средното между двете на тях. Така че, ако мислите за тях като вид увеличаване в от страните, мисля за него като наближите средата, вие искате по този начин. Така че, ако сте били на двете страни на средна, а ние имаме като 5 и 7. Когато ги съберем ли получавате 12, разделяте с 2, е шест. 

Понякога е трудно да се обясни защо това работи, но ако работите чрез пример понякога това ще ви помогне да разберете, ако тя трябва да бъде плюс или минус. Да. 

STUDENT: [недоловим] точно в средата ако те са имали случай, когато там е много по-малък брой и като един голям номер? 

ИНСТРУКТОР: Така че всичко, което трябва е средата на масива. Така че, ако сте имали един куп малки номера и след един наистина голям брой в крайна сметка, това не е от значение. Всичко, което има значение, е, че те са подредени, просто искам да гледам в средата на масива, защото все още сте нацепване на вашия проблем в половината. Cool. Така че сега ние имаме средна, какво ще правим сега? 

STUDENT: сравнение. ИНСТРУКТОР: за сравнение. Така сравнение средната за value_wanted. Cool. Така че виждате тук имаме тази стойност, което искаме тук. Не забравяйте, че това е масив. Така средната отнася до индекса. Така че ние искаме да направим стойности на средната. Не забравяйте, ако искате за сравнение, двойни равни. Можете да направите еднократна равнява сте просто ще я прехвърли, и след това, разбира се, това е ще бъде стойността, която желаете. Така че не прави това. 

Така че отиваме да се види дали стойностите в средата е равна на стойността, което искаме. Не забравяйте скоби. Dropbox трябва да си отиде. Така че това, което правим в този случай? Ако това е, което искаме да се върне? Ние се опитваме да се каже. 

STUDENT: Печат на разстояние. 

ИНСТРУКТОР: Ами, ние не искате да отпечатате. Така че това е булев тук, така че ние искате да се върнете вярно или невярно. Ние казвате, е този брой на [? RRA? ?] Така че, ако това е, ние просто го връща истина. Ако мога да заклинание вярно. 

STUDENT: Защо няма да ви се върне нула? ИНСТРУКТОР: Така бихте могли да върне нула, ако искате. Но в този случай, тъй като нашата функция връща булев, ние трябва да се върне или вярно или невярно. STUDENT: Когато сте казвайки булев израз, можете ли да го определя като равна на фалшива? Например, ако аз искам да кажа, че ако това условие не е изпълнено, като е горната равнява невярно. Ще го разберете, ако просто постави фалшива от другата страна? ИНСТРУКТОР: Да. Така че в действителност, ако сте някога прави нещо като е горната или е по-ниска, който връща истина или лъжа и това е всъщност лош стил речем равнява равнява вярно или равни се равнява на невярна. Вие искате да използвате този резултат както на себе си като на вашия чек. Не е това, което исках. Това е, което исках. Така че в случай на питате за нещо като запазите този в с. 

Така че, ако имаме INT главната (недействителни) и нещо като това. И имате, ако е горната на някакъв вход и сте пита дали можете да направите нещо подобно? Така ли е? STUDENT: Аз се опитвах да го направя [недоловим]. Защото ако it's-- ИНСТРУКТОР: Точно така. Значи вие искате това да бъде фалшива, нали? Студентът: Да. ИНСТРУКТОР: Така че в този случай искам тя да се изпълни, ако това не е вярно. Така готино нещо, което правя е това. Така че не забравяйте, удивителен точка отрича неща? Той казва, че [недоловим] не означава. Така че, ако погледнем само тази част тук, ще се каже, че се изчислява на невярно, колкото искате да. Не е вярно, невярно, които означава това ще се изпълни. Това прави ли смисъл? Студентът: Да. ИНСТРУКТОР: Awesome. OK. Така че бихме могли просто да се върне вярно в този случай. Така че сега ние имаме две други случаите, в този случай. Какви са нашите две други случаи? Нека просто да го направя по този начин. Така че нека да започнем с друго Ако стойностите на средата е по-малко от стойността, което искаме. Така че нашата стойност в средата е по-малко от стойността, която търсим. 

Така че, който граница, което правите мисля, че ние искаме да се актуализира? Горната или долната? Горна? Така че, от коя страна на масива ние ще трябва да се гледаш? 

STUDENT: Колкото по-ниска. 

ИНСТРУКТОР: Ние отиваме да се търсят в ляво. Така друго, ако малка стойност е по-малко. Така средната си стойност тук е по-малко от това, което искаме. Така че ние искаме да приемате от дясната страна на нашия масив. Така че ние ще актуализира ниска нашата граница. Така че ние ще превъзложите ни по-ниска. И какво мислите, че трябва да е по-ниска? STUDENT: Средната стойност? ИНСТРУКТОР: Така средната value-- STUDENT: Plus 1. ИНСТРУКТОР: --plus 1. Може ли някой да ми каже защо имаме, че плюс 1? 

STUDENT: [? Никаква стойност?] е по-равен с него. 

ИНСТРУКТОР: Точно така. Защото ние вече знаем, че нашата средна стойност не е равно на то и ние искаме да го изключи от всички следващи търсения. Ако сте пропуснали, че плюс 1, това ще искал линия за неопределено време. И вие просто ще бъдат уловени в безкраен цикъл и тогава ще segfault и нещата вървят зле. Така че винаги се уверете, че не сте включително стойността, която току-що погледна. Така че ние се грижим за това с един плюс един. 

Така че сега ние имаме последната ни състояние което аз винаги заради безопасността можете да проверите тук, в противен случай, ако стойността на средата е по-голяма от стойността искаме. Това означава, че ние искаме лявата половина ръка. Така че кой ще ходим да се актуализира? Upper. И какво е това ще се равнява? Близкия минус едно, защото Разбира се, ние искаме за да сме сигурни, че не сте гледаше, че средната стойност отново. И тогава ние я имаме. Това е всичко. Това е всичко, двоично търсене е. Това не е толкова лошо, нали? Това е като 10 линии код с бяло пространство. Така че, много мощен, много полезна, ще ви било то с помощта на един от по-късните си psets. Може би не е това, но по-късно. Така че това се учи. Обичам го. Тя ще се отнасят с теб добре. Така Някой има ли въпроси, свързани с двоично търсене? Да. 

STUDENT: Има ли значение дали си п е равна или странно? 

ИНСТРУКТОР: No. Защото ние се хвърли на средата като пад, той просто ще го отреже. Така той ще остане цяло число и тя ще в крайна сметка се справи през всичко. Така че не е нужно да се притеснявате за това. Всеки добър? Awesome. Cool. Така че, вие, момчета, имам това. Slideshow. Така че, както ние говорим за, знам David спомена сложността автономна работа. 

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

STUDENT: [недоловим] first-- ИНСТРУКТОР: Така че средата е най- Първият елемент, който стигаме до, нали? Така че или масив от един или каквото и да търсите само се случва да бъде пляскам потупване по средата. Така че това е нашата най-добрият случай. Вие не можете да получите в реални проблеми, най-вероятно ще достигне [недоловим], че често. Какво ще кажете за най-лошото нашия случай? Най-лошия случай ни е дневник п. И това трябва да се направи с цялото правомощия на две нещо, което говорихме. 

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

Ако сте имали този объркан чанта на номера и казваш, Добре, аз отивам да се провери средата номер и номер Търся е по-малко от това, аз съм просто ще произволно да изхвърли половината. Може би не знаете, ако ви номера в другата половина. Вашият списък трябва да бъдат сортирани. Както е добре, това може да бъде върви напред малко, но трябва да има произволен достъп. Трябва да бъде в състояние само да отидете на тази средна елемент. Ако трябва да преминават чрез нещо или тя ще ви отведе на допълнителни стъпки да стигнем до този среден елемент, това не е влизане н повече, защото добавяте повече работа в нея. И това ще направи малко повече чувство за две седмици, но аз просто вид искаше да предговор, вие даде представа за това какво е да дойде. Но това са двете важни предположения от което се нуждаете за двоичен списък. Уверете се, че е сортиран. Това е най-голямата за вие в момента. И за това ние можем да отидем в остатъка от видове. Така четири sorts-- балон, вмъкване, подбор, и се сливат. Те са всички видове готино. Ако вие, момчета решават да вземат CS 124, вие ще научите за най-различни видове. И ако сте фен XKCD, има е наистина страхотен комикс за като наистина неефективни видове, които съм силно препоръчвам ви ще разгледаме. Един от тях е като паника нещо, което е като, о, не, върнете случаен масив. Shutdown система. Остави. Така че шантавите хумор винаги е добре. 

Така че има ли някой си спомня вид на като само обща представа за това как работи балон вид. Спомняш ли си? 

Студентът: Да. 

ИНСТРУКТОР: Отидете за него. 

STUDENT: Значи става чрез и ако тя е по-голям, тогава вие сменяте двете. 

ИНСТРУКТОР: Мм-хм. Точно така. Така че просто обхождане чрез. Ти провери две числа. Ако този преди е по-голям от този, след това можете просто да ги сменяте, така че в по този начин всички по-голям брой балон нагоре към края на списъка и всички по-ниски числа балон надолу. 

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

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

Така че след това ние гледаме на нашия втори пас. Шест и четири, превключвател. Шест и две, превключвател. И сега имаме няколко неща в ред. Така за всеки така, че ние направи през целия ни списък, ние знаем, че като че много номера в края ще бъдат сортирани. Така че правим трета атака, който е един суап. И тогава на нашето четвърто мине, ние имаме нула слотове. И така, ние знаем, че нашата масив е сортиран. 

И това е най-големия нещо с балон вид. Ние знаем, че когато ние имат нулеви суапове, че означава, че всичко е в пълен ред. Това е нещо за това как ние проверяваме. Така че ние също ще се кодират балон нещо, което също не е толкова лошо. Никой от тях не са толкова зле. Знам, че те може да изглежда малко страшно. Знам, че когато взех класа, дори когато поучаваше класа за за първи път миналата година, Аз бях като, как мога да направя това? Логично е на теория, но как ние всъщност правим това? Което е защо аз също искам да ходя чрез код с вас тук. Така че имам Псевдокод за вас, момчета, този път. Така че просто да се има предвид, тъй като ние сме на път да премине през. Така че ние имаме някакъв брояч, който следи от нашите суапове, защото ние трябва да се уверите, че ние сме проверка на това. И ние обхождане на целия масив тъй като ние просто направихме с този пример. Ако преди елемент е по-голям от елемента след където сме в, ние ги разменят и ние увеличаваме нашето брояч, защото веднага след като сменяте, ние искаме да споделите нашата борба знаеш. Всякакви въпроси там? Нещо изглежда смешно тук. STUDENT: Смятате ли настроите брояча на нула всеки път, когато мине през примката? Не ти продължавай обратно до нула всеки път? ИНСТРУКТОР: Не е задължително. Така че това, което се случва, е, че ние проверете тук. Така че, докато, не забравяйте, това ще се изпълни веднъж без да се провалят. Така че това се случва, за да настроите брояч, равна на нула, След това ще превъртите през. Както се повтаря чрез, тя ще се актуализира брояч. Както се актуализира брояч, когато това е направено, когато той е достигнал края на масива, ако нашият списък не е сортирана, брояч ще са актуализирани. 

Така че след това той проверява състоянието и казва, OK, е контрапродуктивно по-голяма от нула. Ако е така, да го направя отново. Вие искате да възстановите, така че когато проверете, брояч е равна на нула. Ако отидете през сортиран масив, нищо не се променя, това се провали, и вие върнете подредени списъка. Ли, че има смисъл? STUDENT: Тя може по малко. ИНСТРУКТОР: OK. Ако има някакъв друг въпрос, който идва. Да. 

STUDENT: Какво би функцията е за смяна на елементи? 

ИНСТРУКТОР: Така че всъщност можем да напишем че ако ние отиваме в момента. Cool. Така че по тази бележка, Алисън се случва да се върнете към уреда. Това ще бъде забавно. И ние имаме хубава Метод на мехурчето нещо тук. Така че аз вече направих колоездене масива. Ние разполагаме със суапове, че са равни на нула. Така че ние искаме да суап съседни елементи, ако те не са на ред. Така че първото нещо, което трябва да се да се превъртите през нашия масив. 

Е, как мислиш, че биха могли превъртите през нашия масив? Ние имаме за и аз се равнява на 0. Искаме и да бъде по-малко от п минус 1, минус к. И аз ще обясня, че в една секунда. Така че това е една оптимизация тук, където, Спомням си как ми каза след всеки пас чрез WE масив Знам, че каквото и да е on-- 

Така след един пас ние Знам, че това се сортира. След две минавания знаем че всичко това се сортира. След три комбинация ние Знам, че е сортиран. Така, както аз съм итерации масива тук, е това е като се уверите, само да отида чрез това, което ние знаем, е сортиран. OK? Това е просто една оптимизация. Можете да го напиша просто наивно итерации през всичко, тя просто ще отнеме повече време. С този четири контур е просто хубава оптимизация защото знаем, че след всяко пълно итерация масива тук, като всеки пълен цикъл тук, ние знаем, че още един от тези елементи ще бъдат подредени в края. 

Така че ние не трябва да се притеснявате за тях. Ли, че има смисъл за всички? Това готино малък трик? Така че в този случай, ако ние сме итерации чрез, ние знаем, че искате да проверите дали масив п и п плюс 1 са в ред. OK. Така че тук е Псевдокод. Ние искаме да се провери дали масив п и п плюс 1 са в ред. И така, какво може да имаме там? Това ще бъде някакъв условно. Това ще бъде, ако. 

STUDENT: Ако масив п е по-малко от масив п плюс 1. ИНСТРУКТОР: Мм-хм. Е, по-малка или по-голяма от. STUDENT: Над. След това ние искаме да ги разменят. Точно така. Така че сега ние се в това, което е най- механизъм за тях смяна? Така минахме през това кратко време, вид суап функция миналата седмица. Дали някой си спомня как тя работи? Така че не можем просто да ги превъзлагате, нали? Тъй като един от тях ще се загуби. Ако сме казали А е равна на В и след това B е равна на А, всички внезапно двамата са само равна на B. 

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

И тогава ще можем да направим, е да можем да отидем напред и да превъзложите масив п плюс 1, защото ние знаем, имат тази стойност се съхранява. Това е също един от най-големите things-- Аз не знам дали някой от вас има въпроси, по които, ако преминат два реда код изведнъж нещата работят. Поръчка е много важно в CS. Така че се уверете, че диаграмата нещата, ако е възможно за това какво всъщност се случва. Така че сега ние ще превъзлагане масив п плюс 1, защото ние знаем, имат тази стойност се съхранява. 

И ние може да възложи това на масив N или в този случай масив аз. Твърде много променливи. OK. Така че сега ние сме преотстъпва масив аз плюс 1 е равно на това, което е в масив аз. И сега можем да се върнем и зададете масив и с какво? Някой? 

STUDENT: 10. 

ИНСТРУКТОР: 10. Точно така. И едно последно нещо. Ако сме го замениха сега, какво трябва да направим? Какво е едно нещо, че ще ни каже ако някога се прекрати тази програма? Това, което ни казва, че ние имате подредени списък? Ако ние не се изпълняват никакви суапове, нали? Ако суапове е равно на нула в края на това. Така че всеки път, когато се извърши замяна, тъй като ние просто е тук, ние искаме да се актуализира суапове. И знам, че е имало въпрос по-рано за да ви използва нула или едно вместо на вярно или невярно. И това е, което прави този тук. Така че това казва, че ако не суапове. Така че, ако суапове е нула, което винаги съм is-- получите моите истини и ми falses смесват. Искаме ни да се оцени да е вярно и това не е. Така че, ако това е нула, а след това е лъжа. Ако го отрича с [? взрив?] тя се превръща в истина. Така след тази линия се изпълнява. 

Истини и невярна и нули и единици получават луди. Само ако бавно ходи чрез нея той ще има смисъл. Но това е малкото, което този малко код тук прави. Така че това проверява, за да видите сме правили суапове. Така че, ако това е всичко, освен нулев, той ще бъде фалшива и цялото това нещо е ще се изпълни отново. Cool? 

STUDENT: Какво означава прекъсване направя? 

ИНСТРУКТОР: Пробив просто ти избухне на цикъла. Така че в този случай тя ще точно като сложи край на програмата а вие просто ще имате подредени списък. STUDENT: Невероятно. ИНСТРУКТОР: Съжалявам? STUDENT: Защото преди това ние използва писмена 1 над писмено нула да представи, че ако които ще работят или не. 

ИНСТРУКТОР: Да. Така че можете да се върнете нула или 1. В този случай, тъй като ние не сме всъщност правиш нещо с тази функция, ние просто искаме да се счупят. Ние наистина не се грижи за него. Brake също е добро, ако той се използва за излизане на четири линии или условия, които вие не искате да запазите изпълнява. Тя просто ще ви отведе от тях. Това е малко нещо нюанс. Имам чувството, че има много ръка къдрене, като ще научите за това скоро. 

Но вие ще научите повече за това скоро. Обещавам. OK. Така се получи ли всеки балон нещо? Не е твърде лошо. Превъртите през, суап неща с помощта на температура променлива, и ние сме всичко е готово там? Cool. Awesome. OK. Обратно към PowerPoint. Всякакви въпроси, по принцип за това досега? Cool. Мм-хм. 

STUDENT: [недоловим] INT главната обикновено. Трябва ли да има, че за това? 

ИНСТРУКТОР: Така че ние просто търсите точно на действителното алгоритъм за сортиране. Ако го имаше в като по-голяма програма, вие ще трябва пад основната някъде. В зависимост от това къде сте използвате този алгоритъм, тя ще се определи какво е се върна от него. Но за нашия случай, ние сме строго гледа как прави това всъщност обхождане чрез масив. Така че не се притеснявайте за това. 

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

STUDENT: N минус 1. ИНСТРУКТОР: N минус 1. Така че това означава, че има N минус 1 сравнения. Така че едно е да осъзнаем е, че на първата итерация, ние преминем, сравним тези two-- така че това е едно. Тези две, три, четири. Така след една итерация ние Вече имаме четири сравнения. Когато говоря по време на работа и п. N е броят на сравнения като функция на колко елементи имаме. OK? 

Така че проверете, имаме четири. Следващият път, когато знаят, че ние не правим трябва да се грижи за това. Ние сравняваме тези две, тези две, тези две, и ако не сме имали, че оптимизация с четири цикъла, че съм написал, ще се сравняват тук все пак. Така че вие ​​ще трябва да минава през масива и да н сравнения п пъти, защото всеки път, когато ние стартирате чрез нея ние някак едно нещо. 

И всеки път, когато минава през масива, ние правим н сравнения. Така че нашите по време на работа за това е всъщност н квадрат, което е много по-зле в нашата влезете край, защото това означава, че ако имахме четири милиард елементи, това е Ще ни отнеме четири милиарда квадрат вместо 32. Така че най-доброто време на работа, но за някои неща, нали знаете, ако сте в определен набор от елементи Метод на мехурчето може да бъде добре да се използва. 

OK. Така че сега това, което е най-добрият случай Runtime? STUDENT: Нула? Или 1? 

ИНСТРУКТОР: Значи 1 би един сравнение. Точно така. 

STUDENT: N минус 1? 

ИНСТРУКТОР: Така че, да. Така N минус едно. Винаги, когато имате понятие като п минус 1, ние сме склонни просто да го оставиш и ние просто да кажем н защото имате за сравнение всеки от these-- всяка двойка. Така че би било N минус 1, което ние ние току-що се каже, е около п. Когато имаш работа с продължителност на работа, всичко е в доближава. Докато експонентата е вярна, ти си доста добър. 

Това е, как да се справяме с него. Така че най-добрия случай е N, който означава, че списъкът е вече подредени, и всичко, което правим се управлява чрез и проверете дали е сортиран. Cool. Добре. Така че, както виждате тук, ние Просто трябва още няколко графики. Така н квадрат. Fun. Много по-лошо, отколкото п както виждаме, и много, много по-лошо, отколкото дневник 2n. И тогава можете да получите в регистрационните дневници. И вземете 124, можете да получите в като дневник звезда, която е като луд. Така че, ако проявявате интерес, търсене дневник звезда. Това е нещо забавно. Така че ние имаме тази велика диаграма. Само глави нагоре, това е прекрасен диаграма, за да има за средносрочния защото ние дълго, за да ви попитам тези изтънява. Така само за хедс-ъп, имат тази на вашия средносрочна на вашия хубав мамят лист там. Така че ние просто погледна балон вид. В най-лошия случай, п квадрат, най-добрият случай, п. И ние отиваме да погледнем към другите. 

И както можете да видите, единственото един, който наистина се справя добре е сливане нещо, което ще получите в защо. Така че ние ще отидем до следващия here-- вид избор. Дали някой си спомня как Избор на вид е работил? Отидете за него. 

STUDENT: Основно проверете ред и създаване на нов списък. И точно както сте пускането елементи в, ги поставя на правилното място в новия списък. 

ИНСТРУКТОР: Така че звуци по-скоро като вмъкване вид. Но ти си много близо. Те са много сходни. Дори и аз да ги смесва понякога. Преди този раздел, аз бях като, изчакайте. OK. Така че това, което искате да направите, е избор на нещо, начина, по който можеш да се сетиш за това и начина, по който Аз съм сигурен, че не се опитват да получат ги смесва, е тя преминава през и избира най-малкия номер и да го поставя, че в началото на вашия списък. Той я разменя с тази първа точка. Те всъщност са пример за мен. Awesome. Така че просто начин да се мисли за it-- избор вид, изберете най-малката стойност. И ние ще тече през пример което мисля, че ще помогне, защото Мисля, визуализации винаги помагат. Така че да започнем с нещо че е напълно сортиран. Red ще бъде сортиран, зелено ще бъдат сортирани. Всичко това ще има смисъл в секунда. 

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

Сортираните част просто оставят на мира. Мм-хм? 

STUDENT: Как не го знае какво е най-малкото, без да го сравняват за всяка друга стойност в масива. ИНСТРУКТОР: Това го прави сравнение. Харесва ни да го пропуснат. Това е само общото цяло. Да. Когато пишем кода съм сигурен, че ще бъде по-доволни. Но да съхранявате този първи елемент, тъй като най-малката. Можете да сравните и вие се каже, ОК, това е по-малък? Да. Дръжте го. Ето това е по-малък? Не? 

Това е вашият най-малката, я прехвърли към стойността си. И ще бъде много по-щастлив когато ние преминаваме през кода. Така че проверете, ние го сменяте, така че след това ние гледаме на този несортирани част. Така че отиваме да изберете три. Отиваме да го постави на най- края на нашето сортирани част. И ние просто ще продължим да правим , че прави това, и прави това. Така че това е нашият вид Псевдокод тук. Ние ще го кодира тук в секунда. Но просто нещо да ходят чрез на високо ниво. Ти започваш да се премине от и п е равно на 0 до минус 2. Това е друг оптимизация. Не се притеснявайте твърде много за него. Така че, както се казва. Както Яков казва, как правим следите на това, което ни минимум е? Откъде да знаем? Ние трябва да се сравняват всичко в нашия списък. 

Така минималната равнява аз. Това е просто казвам, в този случай индексът на нашата минимална стойност. Така че след това ще превъртите през и тя отива от й се равнява аз плюс 1. Така че ние вече знаем, че това е първата ни елемент. Ние не трябва да го сравни с себе си. Така че започнете да го сравни с другия такава, която е защо тя е и плюс 1 до п минус 1, което е край на масива там. И каза, че ако масив на J е по-малко от масив минути, тогава можем да превъзложите където нашите минимални показатели е. 

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

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

Така че едно е да забележите, всеки време този цикъл се изпълнява, ние започваме с една стъпка по-напред. Когато започнем да погледнем на този един. Следващия път, когато превъртате през, ние започваме по този и тя ни най-малката стойност възлагане. Така че това е много подобен на балон сортиране когато знаем, че след един пас, този последен елемент е сортиран. При избор на вид, това е точно обратното. 

На всеки пас, ние знаем, че първата е сортиран. След втората ПРЕМИНАВАНЕ вторият ще бъдат сортирани. И както си видял с примери на слайд, нашата подредени част просто продължава да расте. Така че от създаването си малкият да масиви аз, всичко, което прави се свива, което ние не търсим най-така, да се намали броят сравнения правим. Това прави ли смисъл за всички? Имате ли нужда от мен, за да тече през тази отново по-бавно или с други думи? Аз съм щастлив да. OK. 

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

Така че това, което ние ще направим ще бъде за една линия. Всеки път, когато трябва да се обхождане чрез масив, ума си може да отиде за една линия. Така че за някои INT к equals-- какво мислим к ще се равнява да започнете? Това е, което ние поставяме като малката стойност и ние искаме да го сравни. Какво искаме да го сравни с? Това ще бъде следващия един, нали? Така че ние искаме к трябва да се инициализира до и плюс 1, за да започнете. 

И ние искаме к в този случай ние вече са размер съхранява тук, така че може просто да използвате размер. Размера, размера на масива. И ние просто искаме да актуализира к от по едно време. Cool. Така че сега ние трябва да намерим най-малкият елемент тук. Така че, ако ние обхождане през него, искам да кажа, ако масив на к е по-малко от най-малката value-- това е мястото, където ние сме всъщност следене на това, което е най-малката here-- След това ние искаме да превъзложите това, което ни най-малката стойност. 

Това означава, че, о, ние сме итерации през тук. Каквато и да е стойност е тук не най-малката ни нещо. Ние не го искаме. Искаме да я прехвърли. Така че, ако ние сме го пренасочване, какво правим мислите, че може да е в този код тук? Искаме да превъзложите малката и позиция. Така че това, което е най-малкият в момента? STUDENT: Array к. ИНСТРУКТОР: Array к. И каква е позицията на предприятието? Какво индексите на ни най-малката стойност? Това е просто к. Така масив к, к, те съвпадат. Така че ние искахме да превъзлагате този. И тогава, след като ние открихме, ни най-малкото, така че в края на този цикъл за тук сме намерили това, което ни най-малък стойност не е, така че ние просто го сменяте. В този случай, като се каже, ни най-малката стойност е тук. Това е най-малката стойност. 

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

STUDENT: За размер, никога наистина го определят или да го промените, как да го разбера? 

ИНСТРУКТОР: Така че едно е да забележите тук е размерът на инт. Така че ние да кажеш в този sort-- сортиране е функция в тази case-- е Избор на вид, той е преминал с функцията. Така че, ако той не бе приет , можете да направите нещо като с дължината на масива или ще превъртите през да се намери дължината. Но тъй като той е преминал в, можем просто да го използвате. Можете просто да приемем, че на потребителя ти даде валиден размер, който всъщност представлява размер на масива. Cool? 

Ако вие имате някакви проблеми с тях или искате повече практика кодиране видове на собствения си, вие трябва да отидете study.cs50. Това е един инструмент. Те имат за проверка, че всъщност може да се пише. Те правят Псевдокод. Те имат повече видеоклипове и пързалки включително тези, които аз използвам тук. Така че, ако все още се чувствате малко размита, опитайте се, че навън. Както винаги, дойде да говори с мен, също. Въпрос? 

STUDENT: Възможно ли е да изречете размер е предварително дефинирано? ИНСТРУКТОР: Да. Размер е предварително дефинирано до тук, в декларацията на функцията. Значи да приемем, че той е бил приет в от потребителя, както и за улеснение, ние ще приемем, че потребителското ни даде правилния размер. Cool. Така че това е избор на вид. Момчета, знам, че ние се учим много днес. Тя е гъста данни за раздел. Така че с това, ние ще за да отидете на вмъкване вид. 

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

STUDENT: Вие сте сравняване through-- ИНСТРУКТОР: Точно така. Вие сте сравняване сам. На всяка итерация, въпреки че ние сме намаляващи това от една страна, все още търсят чрез всичко, за да се намери най-малката. Така че, дори ако вашият най-малката стойност е тук, в началото, все още го сравни срещу всичко останало да се уверите, че това е най-малкото нещо. Така вие ще се окажете минава през приблизително н квадрат пъти. Добре. И това, което е най-лошия случай? Също н квадрат, защото започваш да се прави, че една и съща процедура. Така че в този случай, изборът на вид има нещо че ние също наричаме очакваното изпълнение. Така че в другите, ние просто знам горните и долни граници. В зависимост от това колко луд ни списък е или как е сортиран и да е, те варират между п или п квадрат. Ние не знаем. 

Но тъй като избор вид има същите най-лошото и най-доброто дело, което ни казва, че без значение какъв вид на входа ние имат, независимо дали това е напълно сортирано или напълно обратната подредени, това е ще отнеме същото количество време. Така че в този случай, ако спомняте от нашата маса, всъщност имаше стойност, която тези два вида не са, който се очаква по време на работа. Така че ние знаем, че когато бягаме избор вид, това е гарантирано да стартирате н квадрат време. Не е променливост там. Това е просто очаква. И, отново, ако искате да научите повече, да вземе CS 124 през пролетта. Добре. Виждали сме това. Cool. Така вмъкване вид. И аз най-вероятно ще да гори през това. Аз няма да се налага вие да го кодират. Ние просто ще минеш през нея. Така вмъкване вид е един вид на подобен на избор на сортиране че ние имаме и двете на несортиран и сортират част на масива. 

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

Тъй като вие сте в списък от себе си, са подредени. Поздравления за това, че Първият елемент в този масив. Вие вече сте подредени всички по своему. Така че сега ние имаме сортирано и е сортиран масив. Така че сега ние приемаме на първо място. Какво се случва между тук и тук е, че ние казваме, ОК, ние ще разгледаме в първата стойност на нашата несортиран масив и отиваме да го въведете в правилното място в сортиран масив. 

Така че това, което ние правим, е да вземем 5 и ние казваме, OK, 5 е по-голяма от 3, така че ние просто го поставете дясната правото на това. Ние сме добре. Така че след това преминете към следващата ни един. И ние приемаме 2. Ние казваме, OK, 2 е по-малко от 3, така че ние знаем, че трябва да бъде в пред нашия списък сега. Така че това, което правим е, че ние натиснете 3 и 5 надолу и ние се движат 2 в първата слот. Така че ние просто го поставите в на правилното място трябва да бъде. 

Тогава ние с нетърпение в нашия следващия, и да кажем 6. OK, 6 е по-голям от всичко в нашата сортиран масив, така че ние просто го маркирате към края. И тогава ние гледаме на 4. 4 е по-малко от 6, това е по-малко от 5, но това е по-голямо от 3. Така че ние просто го поставете в полето по средата между 3 и 5. Така че да се направи, че малко малко по-конкретни, тук е един вид на представа за това какво се е случило. Така че за всеки несортирани елемент, ние определи къде в сортиран част е то. 

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

Така че основно, защото е равно на 0 до п минус 1, това е само дължината на нашия масив. Имаме някакъв елемент, който е равен на Първият масив или първите индекси. Зададохме й равно на това. Така че, докато й е по-голяма от нула и масив, J минус 1 е по-голяма от елемент, така че всичко, което прави е като се уверите, че си й наистина представлява на несортиран част на масива. 

Така че, докато все още има неща, да сортирате и й минус един is-- какво е й елемент? J никога не е дефинирана тук. Това е нещо досадно. OK. Както и да е. Така й минус 1, вие сте проверка елементът преди него. Искаш да кажеш, OK, е елемент преди където и да am-- нека всъщност направи това. Така че нека да кажем, че това е като на втория ни пропуск. Така че аз ще бъде равен 1, което е тук. 

Така че аз ще бъде равен на 1. Това ще бъде 2, 4, 5, 6, 7. Добре. Така че нашата елемент в този случай ще бъде равно на 4. И ние имаме някои й, че е ще бъде равна на 1. О, й се намаляващи. Ето какво е то. Така че й е равна аз, така че какво е това поговорка е, че както ние се движат напред, ние просто като се уверите, че ние не сме над индексира този начин, когато ние се опитваме да поставите нещата в нашата подредени списък. 

Така че, когато й е равна на 1 в този случай и масив й минус one-- така масив й минус 1 е 2 в тази case-- ако това е по-голяма от елемент, След всичко това се прави се променя нещата. Така че в този случай, масив й минус едно ще бъде масив нула, което е 2. 2 е не по-голямо от 4, така че това не се изпълни. Така че промяната не се движи надолу. Това, което прави тук, е просто преместване на сортиран масив надолу. В този случай, всъщност, ние може да do-- нека направим този 3. Така че, ако ние сме на разходка из с този пример, ние сега сме тук. Това се сортира. Това е сортиран. Cool? Така че е равно на 2, така че ни елемент е равна на 3. И нашата й е равна на 2. Така че ние гледаме през и ние се каже, добре, е масив й минус едно по-голяма от елемента че ние не търсим най-? И отговорът е да, нали? 4 е по-голяма от 3 и J е 2, така че този код се изпълнява. 

Така че сега това, което правим масив в 2, така че точно тук, ние ги сменяте. Така че ние просто да кажем, OK, масив при 2 сега ще бъде 3. И й се щеше да се равнява на J минус 1, което е 1. Това е ужасно, но вие получите представа. J сега е равен на 1. И масив й е просто ще бъде равна на нашата елемент, който е 4. Изтрих нещо, което не трябва да имате или miswrote нещо, но вие получите представа. 

Той се движи в п. И след това, ако това беше, че ще контур отново и тя ще каже, добре, й е 1 сега. И масив й минус 1 стана 2 е. Има две по-малко от нашия елемент? Не? Това означава, че ние сме Създава този елемент в правилното място в нашия сортиран масив. След това можем да вземем това и да кажем, OK, нашата сортиран масив е тук. И това ще отнеме този номер 6 и да бъде като, добре, е 6 по-малко от тази цифра? Не? Cool. Ние сме добре. 

Направи го пак. Ние казваме: 7. 7 е по-малко от края на нашия сортиран масив? Не. Така че ние сме добре. Така че това ще бъдат сортирани. По принцип всичко това прави го казва излитане първият елемент на Вашата несортиран масив, разбера къде отива в сортиран масив. И това просто се грижи на суаповете за да направите това. Вие сте основно само смяна докато не е на правилното място. Визуалният образ е, че сте движи всичко надолу, като направите това. 

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

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

Така че в крайна сметка е приблизително н квадрат. Ако това е вярно тогава се каже, OK, 2, вие сте добре. 3, което в сравнение с 2. Ти си добър. 4, можете просто да се сравни с опашката. Ти си добър. 6, сравни с опашката, вие сте наред. Така че за всяка точка, ако тя е вече подредени, вие сте едно сравнение. Така че това е просто п. И тъй като ние имаме най-добрия случай по време на работа от п и най-лошия случай по време на работа на п квадрат, ние нямаме очаквания по време на работа. 

Просто зависи от хаос от нашия списък там. И отново, друг графика и друга маса. Така че разлики между видове. Аз съм просто ще бриз през, аз Чувствам се като ние говорихме подробно за това как всички те вид на варира и да се свърже заедно. Така се сливат нещо е последният Аз ще ви отегчавам с момчета. Ние имаме доста пъстра картина. Така се сливат нещо е рекурсивен алгоритъм. И така, да ви момчета знаят какво рекурсивно функция е? 

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

И, всъщност, наистина бързо I може да ви покаже какво прилича това. Така рекурсивни тук, ако погледнем, това е рекурсивни начин да обобщим над масив. Така че всичко, което правим, е имаме функция сума сума, която се размер и масив. И ако забележите, размер понижавания от по един път. И всички го прави е, ако х е равно на zero-- така, ако размерът на масива е равна на zero-- го връща нула. 

В противен случай той обобщава този Последният елемент на масива, и след това отнема сумата от останалата част от масива. Така че това е просто да го счупи на по-малки и по-малки проблеми. Дълга история кратко, рекурсия, функция, която нарича себе си. Ако това е всичко, което имам от това, това е, което рекурсивно функция. Ако сте приели 51, вие ще получите много, много комфортно с рекурсия. Това е наистина страхотно. Той направи смисъл като 3 AM една нощ навън. И аз бях като, защо никога не използвам това? 

Така че за сливане вид, основно какво ще направите, е, че е ще го съборят и да го счупи надолу, докато това е просто отделни елементи. Отделните елементи са лесно да се справи. Ние виждаме това. Ако имате такъв елемент, това е вече се счита сортиран. Така че на входа на наш елементи, ако п е по-малко от 2, просто се върнете, защото това средство е 0 или 1, както сме виждали. Тези елементи се считат сортирани. 

В противен случай тя се счупи на две. Подреди първата половина, се справи със секунда половина, а след това да ги обедините заедно. Защо тя се нарича сливане вид. Така че ние имаме тук ще сортирате тях. Така че ние продължаваме с тях докато е размерът на масива 1. Така че, когато това е едно, ние просто се върнете защото това е сортиран масив, и това е сортиран масив, и това е сортиран масив, ние всички сме подредени. Така че след това, което правим е, че ние започнете да ги сливат заедно. 

Така че начина, по който може да мисли за сливане е просто извадете по-малък номер на всеки от подсекторите масиви и просто да го добавите към появиха масив. Така че, ако погледнете тук, когато имаме тези набори имаме 4, 6 и 1. Когато искаме да се слеят тези, ние гледаме на тези първи две и ние казваме, OK, 1 е по-малък, той отива на фронта. 4 и 6, няма нищо да се сравни да, просто го маркирате към края. 

Когато ние комбинираме тези две, ние просто вземе по-малката от тези две, така че това е едно. И сега ние приемаме по-малък от тези две, така че 2. По-малки от тези две, три. По-малки от тези две, четири, пет, шест. Значи просто издърпване тях. И тъй като те са сортирани по-горе, просто трябва един сравнение всеки път там. Така че по-код тук, просто представителство. Така че започнете от средата и сортирате ляво и дясно и след това просто се слеят тези. 

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

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

Така че аз знам, че е било по-гъста ден. Това не е задължително да става да ви помогне с вашия pset. Но аз просто искам да се направи отказ от отговорност този раздел не е само за psets. All този материал е справедливо игра за вашите midterms. И също така, ако го направите продължи с CS, те са наистина важни основи че ще ви е необходимо да знаете. Така няколко дни ще бъдат малко повече pset помощ, но след няколко седмици ще бъдат много по-действителното съдържание че може да не изглежда супер полезно за вас точно сега, но обещавам, ако продължите нататък ще бъде много, много полезно. 

Така, че това е за раздел. Първа на жицата. Аз го направих в рамките на една минута. Но там ще отида. И аз ще имам понички или бонбони. Има ли някой алергичен към нещо, между другото? Яйца и мляко. Така понички са не? OK. Добре. Шоколадът не? Starburst. Starbursts са добри. OK. Отиваме да има Избухваща звезда следващата седмица след това. Това е, което ще получите. Вие, момчета, имате голям седмица. Прочетете си спец. 

Нека да знаят, ако имате някакви въпроси. Pset две степени трябва да бъдат до вас от четвъртък. Ако имате някакви въпроси, за това как класирани нещо или защо I степен нещо, както аз е, моля пишете ми, дойде да говори с мен. Аз съм малко луд този седмица, но аз обещавам Аз все пак ще отговори в рамките на 24 часа. Така че има голяма седмица на всички. Успех на вашия pset.