[Powered by Google Translate] [Частина 3] [менш комфортно]
>> [Nate Хардісон] [Harvard University]
>> [Це CS50.] [CS50.TV]
>> Гаразд, давайте почнемо.
Ласкаво просимо в 4 тижні CS50.
Якщо ви, хлопці, відкрийте веб-браузер і відкрити PSET 3,
Боротьба з CS50, ми збираємося почати ходити
через ділянку питання там.
Так само, як минулого тижня, ми будемо працювати в CS50 простору,
якщо ви також будете тягти, що як вгору, так,
і якщо ви йдете попереду і по цьому посиланню, що я встав тут на самому верху.
Прийшов час почати роботу.
У нас є наша маленька програма привіт тут. Нічого не божевільний.
Одна з перших речей, які я хочу зробити з вами, хлопці сьогодні йти в протягом декількох рішень
до проблеми Set 1, добрий приклад рішень,
тільки так можна відчути, які коду персоналу пише,
які кодом інші студенти пишуть,
А ви подивіться на це, тому що я знаю, це дивно
коли ви уявити вирішення проблеми набору та отримати коментарі
на вашій власній версії, але іноді це корисно подивитися, як інші люди робили це,
Особливо ті, які є приємні оку.
По більшій частині, я був дійсно вражений рішення, які ви, хлопці виробництва.
Я ще не почав дивитися на ваші 2s завдань, але якщо вони що-небудь на зразок першого,
це нічого не значить, але гарні речі.
>> Якщо ви подивитеся на мої зміни, давайте почнемо всі шляхи вниз по перегляду 1,
і ми збираємося взяти швидкий погляд на вирішення Маріо.
Якщо потягнути цю гру, ці програми, які ми збираємося представити правильні.
Існували не правильність проблем з цими проблемами, а, скоріше,
Ми хочемо трохи розповісти про різних питаннях дизайну
, Які використовувалися тут.
Одна з речей, що було цікаво про рішення
тому, що він використовував цю нову конструкцію, звану фунт визначити,
іноді також називають хеш визначити.
Дозвольте мені наблизити його тут.
# Визначаємо дозволяє давати імена цих цифр у вашій програмі.
У цьому випадку максимальна висота піраміди в Mario
було 23 і, а не покласти 23 в моєму коді
ми хотіли б звернутися до цього як жорсткого кодування 23 -
замість цього дає назву MAX_HEIGHT на цей номер,
так що тут, в моєму зроби той час як цикл
ви можете звернутися до MAX_HEIGHT
замість того, щоб число 23 дюйми
[Студент] Що таке перевага, що робити?
Це велике питання.
Одним з них є читабельність.
Перевага використання цього # визначити є читабельність.
Коли я читаю цей код, я бачу, що відбувається.
>> Я бачу в такому стані, що тут ми тестуємо
на висоту буття <0, що ми могли б також визначені
бути мінімальна висота або висота хв.
Іншою перевагою є те, що потім можна буде прочитати решту частини лінії, щоб побачити
, Що ми також перевірки, щоб переконатися, що висота не перевищує висоту не більше,
тому що ми збираємося продовжувати в той час як висота більше, ніж висота макс.
Іншою перевагою є те, якщо я масштаб трохи тут-
якщо я запускаю цю програму і я запускаю його, скажімо, з 23 прямо зараз,
він буде друкувати всі 23 рядів просто так.
Але сказати, що я хотіла, щоб змінити висоту не більше,
і тепер я хочу, щоб обмежити максимальну висоту піраміди
буде сказати тільки людина, яка була обладнаний.
# Включити , # визначити MAX_HEIGHT,
і скажемо, що ми хотіли, щоб встановити його рівним 10.
Тепер в цей момент, все, що я повинен був зробити, змінити його в цьому місці.
Я можу перекомпілювати код, і тепер, якщо я спробую і введіть в 12,
вона попросить мене знову.
У цьому випадку ми використовуємо тільки MAX_HEIGHT раз.
Це не так вже клопоту, щоб увійти в
і змінити його в той час циклу, якщо вам потрібно.
Але в програмах, в яких ви посилаєтеся той же магічне число
знову і знову, це # визначити механізм дійсно зручно
тому що ви просто змінити його один раз у верхній частині файлу-це правило, де ви помістіть їх-
і зміна просочується через іншу частину файлу.
>> Інші речі, які я хотів би відзначити в цьому призначенні, що я думав, виглядав дійсно хорошим,
один був іменування змінних.
Ви бачите тут, що у нас є цілі змінні називаються рядки і званої висоти.
Простору, хеши, вона допомагає зробити код трохи більш читабельним,
робить його трохи більш зрозуміло, що відбувається насправді.
Це на відміну від використання, скажімо, випадкових літер
або просто абракадабру в цілому.
Останнє, що я вкажу, що в цикли,
Часто ці змінні ітератора, ці лічильники, які ви використовуєте у вашій цикли,
це стандартні і звичайні, щоб почати їх або я, а потім J і K
і відбувається звідти, якщо вам потрібно більше змінних,
і це тільки умовність.
Є багато конвенцій.
Це залежить від мови програмування, який ви використовуєте.
Але в C, ми зазвичай починаємо з я.
Це не має сенсу використовувати, скажімо, або б
в залежності від ситуації.
Ось саме для цього.
Якщо ви зараз підтягти Перегляд 2, ви побачите іншу Маріо,
і це одна схожа на іншу, що ми тільки що бачили,
але він робить щось круто.
Якщо ми подивимося на цей розділ прямо тут, у внутрішньому циклу,
вони використовують деякі божевільні шукає синтаксис тут, прямо в цій лінії.
Це називається потрійний оператор.
Це якщо іншу заяву конденсується в одному рядку.
Умова цій частині в дужках.
Це рівносильно тому, якщо J <висота - I - 1.
А те, що зміст цього блоку, якщо б це простір
, А потім зміст того, що ще буде їсти цей #.
Це, по суті, привласнення простору для цієї змінної.
Це поклавши місце в вміст блоку змінної,
Якщо ця умова виконується, і якщо умова не виконується,
Потім блок змінна отримує цю #.
І тоді, звичайно, замість того щоб будувати цілий рядок
і друк всі в кінці цього рішення виводить її на один символ за один раз.
Досить прохолодно.
>> Ще пару речей, щоб дивитися на. Ми будемо переходити до жадібною.
Тепер, якщо ми подивимося на жадібних, це перше рішення
використовує ці # визначає зовсім небагато.
У нас є одна константа визначена для кожного з різних чисел в цій програмі.
У нас є один для центів за долар, по одній для приміщень, десять центів, нікель і копійки,
і тепер, якщо ми прокрутіть вниз і прочитати код,
ми бачимо стандартний робити-час циклу друку всі з.
Вид суть цієї проблеми, розуміючи, що
Ви, необхідні для перетворення поплавок, який ви читаєте в від користувача до цілого
точно робити математику, і це тому,
з числами з плаваючою точкою, про яку ми говорили в лекції коротко,
це не можливо, щоб точно представляти кожне значення на числовій прямій
тому, що існує нескінченно багато значень між 3 і, скажімо, 3,1 навіть.
Ви можете мати 3,01 і 3,001 і 3,0001, і ви можете продовжувати йти.
Виявляється, всякий раз, коли ви працюєте з грошима, ви часто хочуть, щоб перетворити його
у форматі цілого числа, так що ви не втрачаєте гроші і в такому ж роді.
Роблячи це, і округлення був ключ.
Це рішення використовувати абсолютно простий, великий алгоритм,
яка зменшується кількість залишилися центів, спочатку по кварталах,
то по десять центів, то нікель, то копійки,
і додавши до числа монет кожного разу.
>> Інше рішення, що ми будемо бачити, як я масштаб і перейти до перегляду 4,
були дуже схожі початку, але замість цього використовував справ і мода
Право сюди, щоб розрахувати кількість центів.
Це, число кварталів дорівнює кількості центів розділити на 25,
і причина цього працює, тому що ми робимо цілий підрозділ,
так що це відкидання залишку.
[Студент] Чи є у нас на коментар пошук?
Це дійсно залежить.
[Студент] Ти коментуючи більше, ніж код прямо тут.
Так, і так є купа різних філософій з цього питання.
Моя особиста філософія в тому, що код дійсно правда,
як ваш код є те, що насправді виконання на комп'ютері,
і так ваш код повинен бути читабельним, як можна не вимагають стільки коментарів.
Тим не менше, коли ви робите речі, які є свого роду складним математичним
або алгоритмічно, це добре, щоб коментувати ті, так що ви можете
додати додатковий вимір, додатковий шар до того, хто читає ваш код.
У цих рішень, часто вони прокоментували в більшій мірі тільки тому, що
Ми хочемо мати можливість поширювати їх і є люди забрати їх
і читати їх досить легко.
Але, безумовно, я згоден, що це важко.
[Студент] Але якщо ви сумніваєтеся, йти важчим?
Якщо ви сумніваєтеся, йти важче.
Деякі люди іноді говорять, 0 повернення або щось на зразок цього.
Я думаю, що це смішно коментар.
Очевидно, що те, що відбувається.
Мені не потрібна англійська, щоб сказати мені це.
Іноді люди будуть писати такі речі, як "kthxbai!"
Це мило, але й не-
це не робить різниці між коментуючи точки чи ні.
Такого роду коментарі тільки ха-ха.
Cool.
>> На даний момент, давайте почнемо працювати над проблемою Set 3 розділу запитань.
Якщо ви, хлопці тягнути це знову,
як і минулого тижня, ми не збираємося дивитися шорти в цьому розділі.
Ми повідомимо вам, хлопці, що робити у свій вільний час і говорити про питання.
Але зараз в цьому розділі ми збираємося витратити трохи більше часу,
говорити про меншу кодування основи
як ми це робили минулого тижня, і замість цього, ми збираємося приділяти більше уваги
ще трохи теорії, так що говорити про бінарний пошук, а потім сортування.
З тих з вас, хто стежить разом з лекцією,
може хто-небудь дати мені резюме, в чому різниця
між бінарний пошук і лінійний пошук?
Що відбувається? Звичайно.
Лінійний пошук пошук через кожен елемент в упорядкований список
один за іншим, один за одним,
і бінарний пошук ділить список на 2 групи,
перевіряє, чи має ключі, які ви шукаєте, більше або менше, ніж середина значення
що ви тільки що виявили, і якщо він менший, він йде з меншим списком
і потім ділить це знову, робить ту ж функцію,
весь шлях вниз, поки не знайде середину, щоб бути рівним значенню себе.
Право.
>> Навіщо нам це потрібно?
Чому ми говоримо про бінарного пошуку в порівнянні з лінійним пошуком?
Так.
Двійкові набагато швидше, так що якщо ви подвоїти розмір проблеми
він робить ще один крок, а не в два рази більше.
Саме так.
Це відмінний відповідь.
Лінійний пошук дуже перевірки одного елемента за один раз,
і, як ми бачили в перший день лекцій
, Коли пішов Давид своїм прикладом телефонній книзі
і вирвав одну сторінку з телефонної книги в той час,
і продовжували робити це знову і знову і знову,
він збирається взяти його дійсно багато часу, щоб знайти нікого в телефонній книзі,
якщо, звичайно, він шукав когось на самому початку алфавіту.
З бінарний пошук, ви можете піти набагато швидше,
і це не тільки в два рази швидше або 3 рази швидше, або в 4 рази швидше.
Але проблема стає все менше і менше і менше набагато швидше.
Щоб проілюструвати це, ми почнемо говорити про те, що відбувається
коли ми пишемо бінарний пошук.
Проблема в руці, що якщо у мене є масив чисел,
скажімо, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
, А потім 9 з тонною 0s після нього,
Ми хочемо бути в змозі з'ясувати, чи дійсно швидко, що знаходиться в
це масив чисел.
Я знаю, це здається трохи дурним і трохи надуманий,
тому що зараз вона є.
У нас є масив, який не дуже багато елементів в ньому,
і якщо я попрошу одного з вас, щоб з'ясувати чи дійсно
23 знаходиться в масиві, ви можете зробити це досить швидко
просто глянувши на це і говорив мені: так чи ні.
Аналогових, щоб розглянути є уявіть собі, якби це було, скажімо,
таблицями Excel з 10000 рядків, 20.000 рядків.
Звичайно, ви можете зробити F команда або управління F і шукати щось.
Ви також можете використовувати фільтри і пошук матеріалу,
але якщо у вас переглядати цей файл рядок за рядком за рядком,
це займе у вас багато часу, щоб знайти його.
Це ніби як у прикладі телефонної книги, теж, де
ніхто не дивиться в одну сторінку телефонної книги на час.
Як правило, вони його відкрити до середини,
або, у випадку великої кількості телефонних книг і словників, де
Ви насправді це ключ на першу букву,
Ви клацаєте на що перший лист і відкрити і почати ходити через нього.
>> Нагадайте мені ваше ім'я. >> Сем.
Сем.
Як Сем сказав, що лінійний процес пошуку буде дуже повільним,
, А замість цього з бінарний пошук, як це працює так, що
кожен раз, коли ми проходимо через ітерація нашого алгоритму пошуку,
ми збираємося розділити список в два рази, по суті,
на дві менші списки.
І тоді на наступній ітерації циклу, ми ділимо його знову
в інших невеликих списків.
Як ви можете бачити, проблема стає все менше і менше
бо виконуємо відкидаючи половину списку кожного разу.
Як це викинути роботи?
Так само, як нагадування, що ми збираємося робити, якщо ми були комп'ютерів
і ми були, скажімо, шукає номер 5 в цьому списку
є те, що ми хотіли б вибрати номер у середині.
У середині цього списку, тому що є 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 числа,
Ми б вибрати номер або на 4-й позиції або на 5-й позиції,
і ми називаємо це середині нашого списку.
Виберіть номер в середину.
Тоді, як сказав Сем, ми перевіримо, щоб побачити, якщо це число дорівнює
на номер, який ми хочемо отримати або наш потрібний номер.
Якщо він дорівнює, то ми знайшли його. Ми переможемо.
Якщо це не рівні, то є кілька випадків.
Два випадки або число має бути більше, ніж кількість, ми дивимося на,
або це менше, ніж.
Якщо вона більша, ми рухаємося вправо.
І якщо він менше, ми рухаємося вліво.
І тоді ми повторити весь процес заново
або на правій половині або в лівій половині списку.
>> Перша проблема в розділ сьогодні в тому, щоб з'ясувати,
як ми можемо реально почати, щоб виразити це в код C.
У нас є псевдокод тут.
Те, що ми почнемо робити це я буду тягнути до абсолютно новий простір,
зберегти цей перегляд, так що у нас є ці замітки на потім,
ми видалимо все це, а потім скопіюйте і вставте з проблемою набору
цю інформацію в наших просторах, і, сподіваюся, це не порушує.
Perfect.
Якщо ви, хлопці, все це зробити, скопіюйте і вставте цей код в новий простір,
в порожню.
Давайте спробуємо Даніель. Якщо скомпілювати і запустити цю програму, вона працює?
Номер >> Що він говорить?
Він говорить, що контроль досягає кінця непорожнє функції.
Так, так що дозвольте мені спробувати запустити його.
Хіба ви, хлопці, бачили цього раніше? Чи знаєте ви, що це означає?
Добре, давайте проаналізуємо це небагато.
Він говорив на file.c на лінії 9, стовпець 1 ми маємо помилку, так само, як ви сказали,
і він говорить, що він, випливають з попередження про помилки та попередження возвращаемого типу.
Схоже, щось відбувається з поверненням типу, який має сенс.
У нас є непорожня функція, яка означає, що у нас є функція
, Яка не повертає порожнечу.
Порожнечу функція є той, який виглядає наступним чином:
недійсними Foo (), і це порожнеча, тому що повертаний тип є недійсним,
Це означає, що якщо у нас щось тут
як повернення 1, ми отримаємо помилку компіляції для цього.
Тим не менш, у нас є непорожня функції.
Наші непорожнє функції в цьому випадку наша функція пошуку
тому що вона має возвращаемого типу BOOL.
Коли він говорить, що контроль досягає кінця непорожнє функції,
це тому, що пошук не має возвращаемого заяві.
Це не повертається нічого типу BOOL.
>> Ми можемо виправити це, і що ви думаєте, хлопці
Пошук повинен повернути за замовчуванням?
Яким має бути значення за замовчуванням повернення пошуку?
Тому що це те, що ми можемо поставити в кінці.
Шарлотта, чи є у вас-?
Правда чи брехня? >> Істинним чи хибним.
Який?
False. Я не знаю.
Брехня? Давайте спробуємо.
Чому б вам сказати повернення помилковим? Це відмінна інтуїція.
[Charlotte] я не знаю.
Ми збираємося повернутися помилковим в цьому випадку, тому що це буде нашим замовчуванням
Якщо з якихось причин цей список порожній або голкою
що ми шукаємо не існує.
Потім в самому кінці, якщо ми не повернемося істинної раніше в цій функції,
Ми завжди знаємо, що ця функція буде сказати Ні, це не в масиві.
Це не в стозі сіна.
Тепер, якщо ми скомпілювати і запустити його, дозвольте мені зберегти це таким чином ми можемо потягніть його вгору.
Тепер, якщо ми скомпілювати і запустити нашу програму, він будує.
Ми отримуємо наш маленький рядку.
Якби я вдарив 4-ох-ох.
Це не надрукувати що-небудь. Схоже, що все закінчилося добре.
Ми повинні заповнити цю дюйма
Ми говорили про алгоритм в псевдокоді трохи назад.
Давайте подивимося, крім цього,
і я буду тягнути, що алгоритм назад знову.
Давайте вдарив цього хлопця. Ні.
Там вона є.
Як ми це робимо?
Що б бути хорошою стратегією для рушанні з цим кодом?
Ви повинні вибрати число в середині.
Як ми вибираємо число в середині масиву?
Будь-які пропозиції?
[Студент] STRLEN розділити на 2.
STRLEN розділити на 2. Це один великий.
STRLEN роботи з особливими видами масивів.
Які види масивів?
Струнний масиви, масиви символів.
Це що таке ж поняття, що ми хочемо застосовувати,
але ми не можемо використовувати StrLen, тому що ми не маємо масив символів.
У нас є масив цілих чисел.
Але що StrLen отримати для нас?
Ви знаєте, що це стає для нас?
[Студент] STRLEN змушує нас довжини.
Саме він змушує нас довжини.
STRLEN отримує довжину масиву для нас.
>> Як ми можемо отримати, що в нашій програмі бінарного пошуку?
Як би ви отримати довжину масиву?
[Студент] STRLEN?
Ви можете отримати довжину правильно відформатувати масив рядків C з StrLen.
Проблема, однак, у тому, що ми не маємо масив рядків.
Якщо ми подивимося на цей код, ми повинні це масив цілих чисел.
Як ми знаємо, як довго це?
[Студент] Є еквівалентно одному для кінцевої точки, як Int L або щось?
Виявляється, там насправді немає, і це таким чином, це
одна з тих речей, які просто добре знати про C,
що немає ніякого способу, щоб отримати довжину масиву
якщо все, що я вам це масив.
Причиною він працює з рядками, причина StrLen робіт,
тому що якщо рядок правильно відформатувати,
він буде мати, що спеціальні \ 0 символ в самому кінці.
>> Ви також можете уявити, якщо у вас неправильно відформатованих рядків
і немає \ 0 символ є, то все це не працює.
[Студент] Ви можете додати \ 0?
Ми могли б у цьому випадку.
Ми могли б додати якусь \ 0
або якийсь означає символ, а потім використовувати його.
Але це не зовсім буде працювати
тому що \ 0 для символьного типу,
і тут у нас є цілі.
Інша справа, якби ми використали особливу цінність
як -1, щоб відзначити кінець масиву
Потім ми ніколи не могли б зберігати -1 в нашому цілими масивами.
Ми застрягли.
Виходить, що єдиний спосіб отримати довжину
масиву в C є насправді пам'ятаю
коли ви встановите його, а потім передавати його з масивом
так що всякий раз, коли у мене є функція, яка буде робити деяку роботу
на масив цілих чисел або поплавками чи подвоюється або що там у вас,
Мені також потрібно дати функцією довжини масиву,
і це саме те, що ми зробили тут, у функції пошуку.
Якщо ви подивіться, що ми зробили, коли ми переходимо в нашому масиві тут,
Ми також проходять в довжину, розмір.
Просто так вийшло, що ми назвали цю змінну тут,
цей параметр або аргумент.
Це називається аргументом функції списку або списку параметрів,
і вони також називаються аргументами або параметрами.
Люди використовують різні терміни в різний час.
Я іноді поміняти їх на собі.
Просто так сталося, що ця змінна тут називають аналогічно
до цього # визначити тут.
Але вони не те ж саме.
Капіталізація має значення.
>> Якщо ви подивитеся на те, що тут відбувається, ми заявляємо,
наші Int масиву, який ми назвали цифри.
Ми дали це наш розмір, який відповідає нашому # визначити нагорі.
Це буде 8.
А потім, коли ми потім називаємо нашу функцію пошуку внизу,
ми переходимо до числа ми хочемо знайти, який ми запиті
отримали від користувача.
Ми проходимо у масиві, це числа,
і тоді ми також повинні пройти в розмір масиву,
і те значення розмір 8 отримує зберігається
або передається в це число змінної розміру.
У нас є розмір масиву.
Тепер, якщо ми повернемося до того, про який ми говорили раніше,
Я думаю, Missy виховується такого ступеня, що те, що ми повинні зробити, це отримати довжину масиву
і розділіть його на 2, і що дасть нам точку.
Давайте подивимося.
Чи можу я когось написати цей документ і зберегти його в своєму просторі?
Як щодо Лейли?
Чи можу я вам пишу це в?
Написати перший рядок, де ви берете довжину масиву і отримати середина
і зберігати його в нову змінну.
Я дам вам пару секунд. Чи готові ви?
[Студент нерозбірливо]
Звичайно, я міг вам розрахувати середню точку
в стозі сіна масиву всередині функції пошуку
використанням довжини стозі сіна масив, який є розмір змінної?
Нічого хитрого.
[Лейла] Так же розміру / 2 і просто-
І зберегти його, і натисніть на кнопку Save тут на вершині,
і ми потягніть його вгору.
Perfect.
Там ми йдемо. Awesome.
>> Як, чи буде це скомпілювати?
[Лейла] Ні, вона повинна бути вище.
[Nate] Так, так що ж нам потрібно зробити?
[Лейла] Як Int середині або щось.
Awesome. Так, давайте зробимо це, внутр середину = розмір.
Чи буде це скомпілювати?
Давайте видалити цей коментар і отримати його в бік.
Те, що не буде збирати з цього приводу?
Ми нічого не робимо з цілим,
тому нам потрібно роздрукувати його або щось на зразок цього.
Так, саме так.
Ми отримаємо невикористаних змінних.
Що ще не буде працювати з цього приводу?
Я думаю, що ви сказали щось, Сем. Крапка з комою.
Так, я пропускаю ці крапки з комою.
Це буде постійна річ протягом усього терміну.
Останнє, що я буду робити, я покладу деякі прогалини по обидві сторони
цього оператора тут, так як це зазвичай як ми це робимо
у відповідності з нашим стилем керівництва.
У нас є середина нашого масиву.
Тепер, якщо ми пам'ятаємо, повернемося до нашого алгоритму,
що був другий крок, який ми повинні були зробити, коли в нас середина?
[Студент] Якщо це більше [нерозбірливо].
Так, так що ми повинні робити якісь порівняння, і що ми тут порівняння?
Ви сказали, що якщо вона більше. Що в цьому реченні йдеться?
Число, яке з'являється, якщо це більше, ніж середина, а потім піднятися на масив?
Саме, тому кількість, яка з'являється, коли ми-
Голки, так що ми в порівнянні з голкою,
і що ми порівнянні з голки?
Оскільки голка є те, що ми шукаємо.
Ми порівнюючи його, щоб дістатися до центру.
>> Але це має сенс, щоб перевірити,
якщо середина голки =?
Чи має це сенс?
Хто-небудь не згоден?
Давайте спробуємо, якщо (середина голки ==).
[Студент] Printf ви його знайшли.
[Nate] Е ("Ми виявили, що \ п");
В іншому випадку, я збираюся почати робити щось інше тут.
Я збираюся почати збирати у фігурні дужки, якщо заяви весь час
просто тому, що якщо ми додамо більше матеріалу, то
ми не отримуємо компіляторів.
Так, Сем. У вас є точка.
Проблема в тому, що середина являє собою позиції в масиві,
але ви можете отримати його для представлення значення в цій позиції масиву.
Це велика крапка.
А всі чули, що сказав Сем?
Він сказав, що середина як
являє собою лише позиції в масиві, але це не фактичний елемент в масиві.
Якщо ви думаєте про код, як написано прямо зараз,
якщо ми подивимося на цей масив сюди, яке має 8 елементів в ньому,
, Що є значенням середини збирається бути в цій функції?
[Студент] 4.
[Nate] 4.
Якщо ми подивимося на число 4 -
і ми можемо тільки запустити цей код і покласти трохи сумне обличчя тут
тому що ми не знайшли його, якщо ми запустимо цей код
як це прямо зараз, завантаживши його, будівельні, дозвольте мені прокрутіть униз,
і якщо ми подивимося на число 4,
Ми знайшли його, але ми не отримати цю Printf да.
Однією з причин є те, що ми не повернулися правда,
але ми дійсно знайти номер 4?
І Сем говорить, немає.
Що ж ми бачимо?
Ми дійсно знайшли середину, яка, якщо ми подивимося на масиві сюди,
це буде елемент з індексом 4, що ми дивимося на,
, Що на 23.
>> Як ми насправді отримуємо, що елемент в середині
і не тільки середина себе?
[Студент] Ми хотіли б ввести символ або щось?
Що б це зробити, просто з цікавості?
Ви можете зупинитися трохи докладніше?
Ви повинні перетворити позицію в номер,
так що ви повинні зробити деякі зв'язки, я думаю, що це символ, але воно не може бути.
Так, це хороший момент.
Ми робимо багато такого перетворення позиції в символи, ці символи,
У перших двох наборів проблеми.
Виявляється, що тут, це майже схоже на
доступ до го символу в рядку, якщо це має сенс.
Тут ми хочемо отримати доступ до середини елемента.
Як ми це робимо?
Кевін, у вас є які-небудь пропозиції, як ми могли б це зробити?
Ви можете зробити стіг сіна, відкрита дужка, середні, закриті кронштейн.
Чи можете ви написати, що для нас?
Збережіть його сюди, і ми будемо тягнути, що вгору.
Ми дивимося на цей рядок 9,
і ми, розуміючи, що ми не хочемо, щоб порівняти голку в середині,
але замість цього, ми хочемо порівняти голки
на елемент в позиції середини в нашому стозі сіна масиву.
Cool.
Там ми йдемо.
Так, це виглядає досить добре, якщо (голка == стозі сіна [середина]).
Ми знайшли його.
Тепер, якщо ми запустимо код-Ми резервну копію трохи-
він збирає, вона працює, і тепер, якщо ми подивимося на 4,
ми не знайшли, тому що зараз ми насправді отримати число 23.
Ми отримуємо значення 23, і це те, що ми в порівнянні з нашими голки.
Але це добре. Це крок у правильному напрямку.
>> Саме це ми й намагаємося зробити.
Ми не намагаємося порівнювати голку проти позиції в масиві
а проти фактичного елементів у масиві.
Якщо ми оглянемося назад, зараз знову на наступному кроці в нашому алгоритмі,
який наступний крок?
Лейла вже згадували це коротко.
[Студент] Перевірте, якщо воно більше або менше, а потім вирішити, в який бік рухатися.
[Nate] Так, так, як би нам це зробити?
Чи можете ви поставити в деяких-я зберегти цей перегляд,
а потім, якщо ви покладете в кілька рядків, які будуть це робити.
Так, Шарлотта. >> У мене є питання.
Хіба не повинно бути середина - 1, тому що першою справою
це 0 проіндексовані, тому, якщо ми ставимо 4, що насправді не характер, що ми шукаємо?
Та й інших проблем з цим представляє-
це великий улов, тому що те, що буде в кінцевому підсумку відбувається можливо
якщо ми будемо рухатися і ми ніколи не відрегулювати спочатку?
Я думаю, що ми могли б у кінцевому підсумку роблять намагається отримати доступ до
Елемент на 8-й позиції масиву,
які в даному випадку не існує.
Ми хочемо зробити якийсь облік той факт,
що у нас є нуль індексації.
[Charlotte] Вибачте, я мав на увазі середина - 1 в квадратних дужках.
Ми можемо зробити це.
Ми повернемося до цього питання трохи пізніше.
Як тільки ми починаємо, щоб дістатися до фактичного циклу,
ось тоді ми дійсно бачимо це вступає в гру.
В даний час, ми можемо це зробити, але ви абсолютно праві.
Це нулю індексація буде мати ефект, який ми повинні враховувати.
Давайте подивимося.
>> Як більше і менше ніж?
[Студент] я отримую, як зробити більше і менше, ніж частина.
Я просто не був впевнений, що друкувати, якщо ви виявите, що це менше, ніж стозі сіна середині або більше.
Тут я можу врятувати те, що ДИСК-
[Nate] Так, якщо ви збережете те, що у вас є, і ми будемо потягніть його вгору.
Там ми йдемо.
[Студент] І я ставлю знак питання, що я не знав.
[Nate] Це виглядає здорово.
Тут у нас є знаки питання, тому що ми ще не знаємо,
те, що ми збираємося зробити ще досить.
Що ми хочемо зробити-ой, у нас є деякі дужки все фанкі на нас.
Ми виправимо ці дужки.
Там ми йдемо.
І те, що ми хочемо зробити, на нашу алгоритмом,
якщо ми не знайдемо голку?
Скажімо в разі, якщо голка менше, ніж те, що ми дивимося. Кевін.
Тільки подивіться на ліву половину.
Право, таким чином, ми поставимо коментар тут, який говорить «подивіться на ліву половину".
І якщо голка більше стіг сіна в середині, що ми хочемо зробити?
[Студент] Тоді ви подивіться на праву половину.
Подивіться на праву половину ", подивіться на праву половину".
Не так вже й погано.
Отже, на даний момент, все виглядає досить добре.
Проблема з кодом, як написано це що?
[Студент] У вас немає кінцевих точок для половини.
Так, у нас немає кінцевих точок для половини.
Ми тільки збираємося пройти через це один раз.
Ми тільки збираємося дивитися один на середину.
Будь-який елемент є, або її немає.
Для того щоб завершити це, ми повинні будемо зробити якийсь повторення.
Нам потрібно повторювати до тих пір поки ми бачимо, що
або елемент знаходиться там, тому що ми звузили і, нарешті, знайшов його,
або його там немає, тому що ми дивилися через всі речі,
у відповідних половинах масиву і виявив, що немає нічого там.
>> Всякий раз, коли ми отримали це повторення відбувається, що ми будемо використовувати?
[Студент] цикл.
Якась циклу. Так.
[Студент] Чи можемо ми робити-поки петля і він це зробити і то при
голка не одно-я не впевнений, де я збираюся з цим.
Але ніби як це зробити, поки вона не дорівнює значенню, користувальницький введення.
Так, так що давайте подивимося, як це могло б написати сам?
Ви сказали, що давайте використовувати DO-циклу.
Де зробити старт?
[Студент] Відразу після розміру / 2.
[Nate] Добре, і що ж ми будемо робити?
Ми заповнити пізніше.
Що ми будемо робити?
[Студент] Не ми хочемо зробити все те, що ми маємо у випадку частина?
[Nate] Чи подобається всі ці речі, здорово.
Копіювання і вставка.
О, Боже.
Давайте подивимося, якщо це працює, якщо ми можемо вкладки над цим.
Красива.
Добре, і ми зберігаємо це так, ви, хлопці, є.
Все в порядку, і ми збираємося робити це в той час,
те, що було за умови, що ви були після?
[Студент] У той час як голка не рівні, так як знак оклику.
Але я не впевнений точно, що це таке ще.
[Nate] Так, це один із способів зробити це.
Сем, у вас є коментарі?
[Сем] я згадав, коли я дивився на відео,
Я взяв скріншот одного з подібних, коли ми робили псевдокод для нього,
була деяка зв'язок між макс і мін.
Я думаю, що це було щось подібне, якщо Макс все менше хв.
Є.
[Сем] Або як якби Макс не менше, ніж хв або щось на зразок цього,
тому що це буде означати, що ви шукали все.
>> Так, так що ж це звучить як максимальний і мінімальний мали на увазі?
[Сем] Значення, які, цілі числа, які збираються змінити
щодо того, де ми ставимо крапку.
Саме так.
[Сем] У цей момент він збирається [нерозбірливо] обчислити макс і мін.
Середина це максимальний і мінімальний ідея.
Чи має це сенс для людей?
Якби ми були, щоб почати дивитися на те, як ми збираємося це зробити ітерацію,
Ви абсолютно праві, що ми хочемо використовувати якісь робити, в той час як петля.
Але я думаю, якщо ми згадаємо, що відбувається на місці цього масиву
і те, що відбувається насправді, я збираюся писати тут-
на найпершій ітерації бінарний пошук, маємо-
Я збираюся використовувати б і е для позначення початку.
А потім в кінці нашого масиву.
Ми знаємо, що початок на 4 прямо тут,
і ми знаємо, що кінець на 108.
Скажімо, ми шукаємо число 15.
Перший раз, коли ми робимо це, як ми бачили раніше,
середина або буде 16 або 23
в залежності від того, як ми обчислимо речі.
З рівномірного розподілу в середині дасть нам це простір
між 16 і 23, ми не можемо розділити його нарівно
або розділити його і отримати на справжню середину.
Ми будемо дивитися на 16.
Ми розуміємо, "Гей, 16> 15, які ми шукаємо".
Щоб потім подивіться на ліву половину масиву
те, що ми в кінцевому підсумку робить, відкидаючи
це вся верхня частина
і каже: "Добре, тепер наша кінцева точка буде тут".
Наступна ітерація нашого циклу, ми тепер, дивлячись на цей масив,
ефективно відкинувши цю частину, тому що тепер
якщо ми беремо середину, щоб бути різниця між початком і кінцем,
ми знаходимо нашу середину, щоб бути 8,
які ми можемо перевірити 8 щоб побачити, де він знаходиться в залежності від числа ми шукаємо,
15, знаходимо, що 15 більше,
таким чином, ми повинні рухатися до правої частини списку,
яких ми знаємо, тому що ми люди, і ми можемо побачити його.
Ми знаємо, що права частина збирається бути там, де ми його знаходимо,
але комп'ютер не знає, що, таким чином, що ми будемо робити це ми будемо насправді
було це піти, і тепер на початку і в кінці
знаходяться на тому ж місці, так що середина стає єдиним номером у списку в той момент,
, Що на 15, і ми знайшли його.
Чи означає це, пролити світло на якому все це максимальний і мінімальний позначення йде,
відстеження кінцевих точок масиву для того, щоб з'ясувати,
як звузити речі вниз?
>> Що б сталося, якби це було не рівним 15 зараз?
Що робити, якщо ми шукали 15 і, замість цього, це число було також 16?
Ми б сказали: "О, це більше.
Ми хочемо повернутися до лівих ".
І ми б рухати нашу електронну вправо,
в цей момент у нас є кінцева точка, яка була б суперечливими.
Він не зміг би знайти більше елементів
тому що тепер у нас є кінцева точка і наша початкова точка,
Макс наших і наших хв, зараз перевертається.
Ми пошуку по всьому масиву. Ми не можемо нічого знайти.
Це точка, в якій ми хотіли б сказати: "Добре, ми збираємося, щоб зупинити цей алгоритм.
Ми нічого не знайшли. Ми знаємо, що це не тут ".
Як це відбувається?
[Студент] Як саме комп'ютер перемикання кінця?
Як в кінці кінцевому підсумку перед початком?
Зрештою перед початком
у зв'язку з математикою, що ми збираємося робити кожен раз, коли ми робимо це.
Те, як ми помінятися, якщо ви подивитеся на самий перший раз ми це робимо своп
де у нас почало в 4 і в кінці
на всьому шляху вниз на 108 і наші середина, скажімо, в 16 -
Я збираюся скинути це назад в 15-якщо ми шукаємо 15,
Ми знали, що те, що ми зробили, коли ми перевірили 16 і побачив, що це було більше,
і хотів відкинути всю праву частину списку,
Ми побачили, що те, що ми хотіли зробити, це перейти цю електронну прямо тут.
По суті, електронний були переміщені в один до середини.
Аналогічним чином, коли ми зробили це ітерації алгоритму
і середина була на 8,
ми виявили, що 8 <15, тому ми хотіли, щоб перемістити б
наступний за середину.
Тепер, на початку і в кінці обидва разом в цьому 15.
>> Якби ми відбувалися шукати якісь інші цінності, а не 15,
або, якщо це 15 замість цього було 16,
ми б виявили, що електронна ми хочемо, щоб перемістити один до середини.
Зараз в електронній б там перекинувся менше, ніж б.
Давайте розглянемо, як ми насправді в кінцевому підсумку цей алгоритм кодування.
Ми знаємо, що ми хочемо, щоб ця середина розрахунок.
Ми також знаємо, що ми хочемо, щоб відслідковувати початок і кінець масиву
наші поточного масиву, щоб ми могли зрозуміти,
де ця лівій половині списку, а де права половина списку.
Ми робимо це або початок і кінець,
або ми можемо називати їх мінімальний і максимальний.
Я буду використовувати починаються і закінчуються на цей раз.
Коли ми починаємо, якщо ми оглянемося на нашому прикладі тут,
наші початку був встановлений на самому початку масиву, як природний.
Що індексу це було? Якою має бути наша почати?
Данило.
[Даниїл] Haystack [0].
[Nate] Так, щоб ми могли встановити його рівним стозі сіна [0].
Проблема, однак, у тому, що це дає нам не позиція першого елемента.
Це дає нам індекс першого елемента або фактичне значення в цій першій позиції.
[Студент], який буде конвертувати в 0,20?
[Nate] Що це буде зробити, це, ну, він не буде робити будь-які перетворення.
Що він буде робити це він буде зберігати 4 в почати,
і тоді це буде важко зробити порівняння з початку
тому що Бегін буде проводити значення 4,
, Який є початком нашого масиву,
але ми хочемо, щоб відслідковувати індекси в масиві
на відміну від значень.
Ми насправді використовувати 0, як цей.
На кінець масиву Шарлотта принесла це трохи раніше.
Це те, де ми будемо брати до уваги нуля індексації.
>> Шарлотта, що до кінця масиву?
Що таке індекс кінця?
[Charlotte] Розмір - 1.
Так, і розмір якої ми повинні використовувати?
Чи повинні ми використовувати розміром капіталу або рядкова розмір?
Капітал розміром.
У цьому випадку ми могли б використати розміром капіталу.
Якщо ми хочемо цю функцію, щоб бути портативними
і використовувати цю функцію в інших програмах,
ми дійсно можемо використовувати рядкові розміру.
Це теж добре.
Але Шарлотта абсолютно правильно, що ми хочемо мати розмір - 1.
На даний момент-
[Студент] Як вийшло, що ви можете використовувати заголовні розмір?
Як виходить, що ми могли б використовувати заголовні розмір?
Виявляється, що ці # визначає, дійсно,
під капотом, текст, як знайти і замінити, якщо це має сенс.
При компіляції коду етапі попередньої обробки
укладача проходить через файл,
і він шукає скрізь, що ви написали розміром капіталу,
і він замінює, що текст буквально з 8, як і що.
У цьому сенсі, це дуже відрізняється від змінної.
Це не займе ніякого місця в пам'яті.
Це простий трюк заміна тексту.
У цьому випадку, ми збираємося використовувати розмір.
Звідси ми хочемо зробити свого роду повторення,
і ми на правильному шляху з нашим DO-циклу.
Ми хочемо зробити щось, поки умова не виконана більше,
і, як ми бачили раніше, ми побачили, що ця умова
дійсно, що ми не хочемо кінця
бути менше, ніж починатися.
>> Це наша зупинка стані.
Якщо це відбудеться, ми хочемо, щоб зупинитися і оголосити, як: "Гей, ми не знайшли нічого".
Щоб виразити це, ми хочемо використати якийсь цикл.
У цьому випадку, було б зроби той час як цикл, цикл, у той час як цикл?
У нас є зроби той час як цикл тут.
Ви, хлопці, як цей підхід?
Як ви думаєте, ми повинні спробувати інший підхід?
Кевін, які думки?
Ми могли б якийсь час циклу, тому що ми знаємо, максимальна
буде більше, ніж хв на початку будь-якому випадку.
Так, так що немає ініціалізації, що має статися.
Ті, зроби той час як петлі здорово, коли у вас є щось для ініціалізації
до цього тестування, а тут
Ми знаємо, що ми не збираємося тримати повторної ініціалізації як починати і закінчувати
кожен раунд циклу.
Ми знаємо, що ми хочемо ініціалізувати їх, а потім перевірити наш стан.
У цьому випадку, я насправді піти з простою цикл час.
Виявляється, що робити, у той час як петлі використовуються досить рідко.
Багато місця навіть не вчать робити під час циклів.
Вони гарні для обробки користувальницького введення, таким чином, ми бачили, багато з них до цих пір.
Але нормально і поки петлі набагато більше спільного.
Виявляється, що це умова, як написано
Не буде дійсно нам дуже добре, і чому це?
Мені дуже шкода, я не знаю вашого імені.
Я Джері. >> Вибачте?
Це Б-О-Р-У-I.
Ну, гаразд.
Я не бачу тебе в моєму списку.
Ах, це тому, що-о-о, це має сенс.
У вас є уявлення про те, чому це поки петля не може працювати, як задумано,
як написано з умовою?
[Jerry] Ви маєте на увазі, як ви хочете, щоб всі речі після того, як в-?
Так, так от один.
Ми могли б покласти всі ці речі в той час як цикл, що є абсолютно вірно.
Інша справа, що це трохи більш проблематично, однак, є те, що ця умова не працює.
[Студент] Вам потрібно перевернути його.
Право, таким чином, ця умова ніколи не буде істинним спочатку, як ми говорили про це.
Ми хочемо зробити щось до кінця <початися,
але ми хочемо зробити щось у той час як
почати ≤ кінця.
>> Там у зверненні, що логіки немає.
Я винен робити тих помилок, весь час.
[Студент] Чому це повинні бути меншими або дорівнювати?
Тому що ви пам'ятаєте випадок, коли ми дісталися до
де був тільки один елемент, і ми були внизу,
і ми шукали якраз в 15 в нашому масиві?
І наш початок і кінець наш був того ж елемента.
Ми хочемо, щоб переконатися, що ми працюємо в цьому випадку.
Якщо б ми зробили пряму менш,
Ми б тільки бути в змозі отримати до 2-елемент масиву.
Як тільки ми дісталися до останнього елемента, що, якщо б це було наше елемент, ми ніколи не знайти його.
Тепер ось, ми можемо зробити так само, як ви говорили.
Ми можемо почати plopping речі прямо в середину нашого циклу.
Ми можемо грюкнути в нашій середині.
Ми можемо взяти все це, якщо заяви,
витягнути їх з цього зроби той час як цикл,
ляснути їх,
очистити речі трохи,
і я буду йти вперед і зберегти цей перегляд.
І в цей момент, ми отримуємо досить близько.
Сем.
Я думаю, ви також повинні мати Int середину = розмір - 1/2.
Зрозумів, розмір - 1/2.
Чи є що-небудь ще нам потрібно змінити в цій лінії?
Це був гарний улов.
>> Що ж розміру робити? Невже ми постійно змінюється розмір?
Для того, щоб тримати лінію, як це, ми повинні змінити розмір.
Ми повинні змінити розмір кожного разу, коли ми йдемо навколо циклу.
Але пам'ятаєте, коли ми йшли через наш приклад лише трохи вище,
і у нас був початок на 4
і в кінці всі шляхи на 108?
Як ми обчислимо середню точку?
Якби ми, використовуючи розмір?
Або ми використовували починаються і закінчуються, а?
Це різниця між кінцем і початком.
Ось саме, і як саме я повинен написати, що Шарлотта?
Просто кінець - початок.
Вам не потрібно буде робити - 1
тому що - 1 була включена в кінці кінців, і починаються вже.
[Nate] Відмінно, ви абсолютно праві.
Ми не повинні робити - 1, тому що це - 1 були включені
і склала при ініціалізації в кінці змінної.
>> Чи є що-небудь ще мені потрібно зробити, синтаксично, щоб ця лінія має сенсу?
[Студент] Plus почати. ​​>> Plus почати?
[Студент] в кінці.
Тому що він розраховується тільки на половину довжини.
Вам потрібно додати початися.
[Nate] Що б це обчислити для нас?
Якщо ми думаємо про кінець на цій самій першій ітерації,
Кінець буде в позиції індексу 7.
Початок знаходиться в положенні 0.
Пам'ятайте, що ми шукаємо або
положення 3 або позиції 4.
Якщо ми подивимося на цю математику, просто щоб зробити його трохи більш відчутним,
поставити деякі номери тут, у нас є 7, 0,
так 7 - 0, а потім / 2
становить 3 в цілочисельне ділення, тобто.
Тоді нам потрібно, щоб потім додати туди наш почати?
Ми не в цьому випадку.
На найпершій ітерації, то це буде чудово, тому що Бегін 0.
Але, як ми прогрес, ми робимо дійсно все, просто потрібно
кінець - почати / 2.
Там ще одна хитрість, і це саме одна з пріоритет.
[Студент] Чи потрібно нам дужки?
[Nate] Точно, і це тому, що якщо ми не будемо ставити ці дужки,
Потім цей рядок буде інтерпретуватися, а
як (кінець) - (початок / 2), який ми безумовно не хочемо.
Слідкуйте за тим, правила пріоритету.
[Студент] Чому вона не закінчиться + почати?
Чому вона не закінчиться + почати?
[Студент] Чому це не так?
Чому б це було +?
Я думаю, що ви маєте рацію.
[Студент] Тому що це середня?
[Nate] End + почати, ви абсолютно праві.
Нічого собі, я повністю goofed. Ви праві.
Якби ми робили мінус, ми хотіли б додати починати масштаб
У цьому випадку, ви дуже правильно, що ми хочемо взяти середнє з двох,
тому ми хочемо, щоб додати їх, на відміну від відняти їх.
[Студент] Він також буде працювати, якщо ви зробили кінця - розпочинати / 2 + початися.
Він би, якби ми, я так вважаю.
>> Наприклад, якщо ми дивимося на початку,
і ми перемістили його сюди
до 15.
Тепер починається в позиції 2.
Остання знаходиться в положенні 7.
Якщо відняти їх, ми отримаємо 5.
Розділіть це на 2, отримуємо 2.
І тоді ми додаємо 2 назад,
і що отримує нас на 4-й позиції,
який знаходиться прямо тут, яке є серединою.
[Студент] Чи потрібно нам, щоб піклуватися про обгортання?
В якому сенсі ми повинні дбати про обгортання?
Якщо сума або різниця між
в залежності від того, як ми робимо це не парне число.
Потім комп'ютер заплутається чи, коли це 2,5;
Ви рухатися вліво або вправо, щоб визначити, що є середина?
Є.
Виявляється, що з цілочисельне ділення,
Ми ніколи не отримаємо ці числа з плаваючою точкою.
Ми ніколи не отримаємо десяткову.
Це повністю відкидаються.
Якщо у вас є комп'ютер розділити два Int змінні,
і одна 7, а інший 2,
Ви не будете отримувати 3.5 в якості результату.
Він буде отримувати 3.
Решта будуть відкинуті, так що це ефективно округлення
Не кругла, а скоріше підлозі, якщо ви, хлопці, знайомі з цим в математиці,
де ви повністю відмовитися від десяткової,
і так ви, по суті обриву вниз до найближчого
Усього позицій, до найближчого цілого числа.
[Студент] Але тоді це проблематично, тому що якщо у вас є масив з 7 елементів
Потім, що автоматично робить 3-й елемент з середини, а не 4-й.
Що нам робити з цим?
Це проблематично, тому що якби ми мали масив 7,
було б вибрати 3-й, а не 4-й.
Могли б ви пояснити трохи більше?
[Студент] Тому що, якщо у вас є 7 елементів, то 4-й елемент
буде середина, вірно?
Пам'ятайте, Ваша думка про те нуля індексується, хоча.
[Студент] Так, так і в положенні 3. Це буде середина.
Так.
Ну, гаразд. Я розумію, що ви маєте на увазі.
Це трохи дивно, так як ми звикаємо до цього саме поняття
позбутися знаків після коми.
Це велика крапка.
Давайте закінчимо це.
Ми розрахована наша середина.
>> Ми тестування, щоб побачити, якщо наші голки дорівнює середній вартості.
Ми друкуємо, що ми його знайшли, але насправді, те, що ми хочемо зробити в цій ситуації?
Ми виявили, тому ми хочемо, щоб зухвала знаємо, що ми його знайшли.
У нас є функція, яка це логічне типізовані функції.
Те, як ми сигналізувати про це викликає наші функції, які ми готові піти
це ми говоримо: "Ей, це правда".
Як би ми це зробимо, Кевін?
Ви киваючи головою. >> [Кевін] Додати повернення правда.
[Nate] Точно, повернути істинний.
Тепер, якщо це не рівні, як би ми подивимося на ліву половину?
Будь-які ідеї?
Стелла, які ідеї?
Вам необхідно встановити нову позицію кінця.
Так.
Таким чином, ми повинні зробити положення середина - кінець.
Великий.
Нам необхідно створити нові позиції на кінець
дивитися на ліву половину.
Це було те, що ми говорили раніше, де
Я продовжую повертатися до цього прикладу.
Я починаються тут, а то у мене в кінці всі шляхи сюди.
>> Знову ж таки, якщо ми дивимося на 15, і наша середина знаходиться на 16,
і ми розуміємо, "Oops, 16 більше.
Ми хочемо, щоб перейти до лівій половині ".
Ми б потім перемістіть кінець 15,
і ми робимо, що, взявши в бік від середньої точки
і установка, що наші нові кінця.
Точно так само, якщо ми хочемо, щоб дивитися на праву половину, як би ми це робимо?
У Вас є ідея?
[Студент] Ви тільки що встановили починають мідпойнте + 1.
[Nate] Великий.
І тепер у випадку, якщо ми не знайдемо нічого,
нічого, що отримати подбали для нас?
Даніель, не отримаєте, що поклопоталися про нас?
[Даниїл] Немає
[Nate] Якщо ми зробимо це через весь масив, і ми нічого не знайдемо,
де б, що будуть піклуватися, або ми повинні піклуватися про нього?
[Данило] в той час як стан.
[Nate] Так, в той час як стан, точно.
Вона буде піклуватися про проходять через весь масив, якщо ми нічого не знайдемо.
Це в той час як цикл завершиться.
Ми ніколи не стикалися з цією умовою,
і ми можемо повернутися помилковим.
Ми також можемо залишити це, якщо тут, як це
тому що, якщо це, якщо твердження вірне,
і наша функція буде повертати,
і таким чином ми суттєво скасування цієї функції в цій точці
Коли ми повернемося правда.
Але що відбувається з цією структурою тут?
Чи буде це працювати зовсім, або є логічний вада там?
>> Існує певний логічний вада в наявності, з тим, як він налаштований.
Що може бути?
[Студент] Навіщо вам потрібен - і + 1с?
Це відрізняє наш масив, щоб бути наша нова ліва половина і права половина.
[Студент] Але чому ти не міг зробити це без - 1 і + 1с?
[Nate] Ми могли б встановити його рівним середина?
Що може бути проблематичним з цього приводу?
[Студент] Я думаю, це неефективно, оскільки ви перевіряєте значення, які вже перевірені.
[Nate] Точно, так що Сем абсолютно праві.
Якщо ви встановите кінця і почати одно середина
замість - 1, + 1 задумливо,
в якийсь момент в майбутньому ми закінчимо перевірку середину знову.
[Студент] Я почав PSET, а потім у мене було щось на зразок цього
де я забув + 1, і воно застрягло у нескінченному циклі.
Правильно, тому що в якийсь момент ви ніколи не збираюся починати і закінчувати
насправді перетинаються.
Cool.
Там ще один логічний вада, і що, що це обов'язково має бути
ще, якщо.
Чому це може бути?
>> Причина в тому, якщо це не ще, якщо-ти бачив це, Кевін?
[Кевін] Так, тому що ви зміни кінцевої точки.
[Nate] Саме так.
Ми міняємо кінцевої точки,
і якщо воно написано, як це зробити-Ми простору між-
вона буде перевіряти цей випадок.
Цей випадок, якщо це вдасться, перерве з функції.
Тоді вона буде перевіряти наступному випадку,
і якщо це вдасться, він буде регулювати кінцеву точку,
а потім він буде продовжувати і перевірити цей випадок.
Але на даний момент, ми не хочемо, щоб продовжити перевірку.
На щастя, ми не скидається середини тут,
і ми знаємо, що це справа не вдасться.
Але ми безумовно хочемо покласти ще, якщо там
хоча, що може бути в даному випадку
так як ми не підлаштовуючись середину, яка б змінити ситуацію?
Ні, тому що ці випадки є винятковими.
Знову ж таки, мій поганий.
Ми не, я думаю, потрібно це ще, якщо.
Ми можемо дати йому спробувати і запустити його і подивитися, що відбувається.
Будівництво, сталася помилка.
Це, напевно, тому що я залишив ці б в і е в тут.
Чи є у мене більше тих, нагорі?
Це не схоже на це.
Ми масштаб, будівництво,
там вона йде, так що тепер, якщо ми шукаємо 15,
Так.
Дозвольте мені змінити масштаб зображення
15, да. Ми можемо запустити його знову.
Завантаження вихідного коду, будівництво, працює.
Ми можемо шукати щось подібне 13,
і ми нічого не отримуємо роздруківку, так що це не знаходячи, що для нас.
Це здорово, тому що це не в нашому списку.
>> Зараз ми знаходимося поза часом.
Це буде його на цьому тижні.
Спасибі, що приєдналися, і побачимося.
>> [CS50.TV]