[Музика грає] 

ZAMYLA Чан: Перше, що ви могли б повідомлення про знахідку є те, що ми вже вже код, написаний для нас. Це називається код розподіл. Таким чином, ми не тільки написання власного код з нуля більше. Швидше, ми заповнення пустот в деякому попередньо існуючого коду. 

Програма find.c запрошувати номера заповнити стіг сіна, пошук стозі сіна для користувачів представлених голки, і він робить це шляхом виклику роду і пошуку, функції, визначені в helpers.c. Так find.c написано вже. Ваше завдання написати помічників. 

Так що ми робимо? Ми реалізації дві функції. Пошук, який повертає істину, якщо значення знаходиться в стозі сіна, повертаючись помилковим, якщо значення не в стозі сіна. А потім ми також здійснює роду яка сортує масив з ім'ям значення. 

Так що давайте вирішувати пошуку. Пошук в даний час реалізована у вигляді лінійний пошук, але ви можете зробити набагато краще, ніж це. Лінійний пошук здійснюється в O часу н, який є досить повільним. Хоча, він може шукати будь-який список дано йому. Ваше завдання полягає в реалізації бінарний пошук, який під час виконання O з журналу п. Це досить швидко. 

Але є застереження. Довічного пошуку можна тільки пошук через попередньо відсортованих списків. Чому це відбувається? 

Ну давайте подивимося на прикладі. Враховуючи масив значень, стіг сіна, ми збираємося шукати голки. І в цьому прикладі ціле три. Таким чином, що бінарний пошук працює так, що ми порівняємо середню вартість масив до голки, так само, як, як ми відкрили телефонну книгу на середині сторінки в нульовому тиждень. 

Таким чином, після порівняння середнє значення для голка, ви можете відмовитися від або вліво або права половина масиву затягнувши свої кордони. У цьому випадку, так як три, наша голка, менше 10, середнє значення, Право межа може зменшуватися. Але спробувати зробити ваші кордону як можна щільніше. Якщо середнє значення не голка, то ви знаєте, що вам не потрібно, щоб включити його до цієї категорії. Таким чином, ви маєте рацію межа може затягнути пошук кордону трохи більше, і так далі і тому подібне до ви знайшли голку. 

Отже, що ж псевдокод виглядати? Ну а ми все ще переглядаючи список і досі елементи дивитися в, ми беремо середину списку, і порівняти, що середнє значення для наша голка. Якщо вони рівні, то це означає, що ми в знайшла голку, і ми можемо повернутися вірно. 

В іншому випадку, якщо голка менше середнє значення, то, що означає, що ми можна відкинути праву половину, і просто пошук по ліву сторону масиву. В іншому випадку, ми будемо шукати Права частина масиву. І в кінці, якщо ви не маєте будь більше елементів зліва пошук, але ви Нічого не знайшли голку ще, то ви повернутися помилковим, тому що голка безумовно не в стозі сіна. 

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

Тепер давайте подивимося на роду. Сортувати приймає масив і ціле п, що розмір масиву. Зараз є різні типи в дусі, і ви можете дивитися на деякі шорти для демонстрацій і пояснень. Повертається тип для нашого Функція сортування, є нікчемним. Так це значить, що ми не збираємося повернутися будь-який масив з роду. Ми насправді збирається міняти дуже Масив, який був прийнятий в нас. 

І це можливо, тому що масиви передаються за посиланням у С. Тепер ми см. про це трохи пізніше, але Істотна відмінність між передачею в чимось на зразок ціле і проходження в масиві, в тому, що, коли ви перейти в ціле число, C тільки збирається зробити копію цього цілого і передати його функції. Оригінальний змінна не буде змінена Після того, як функція закінчена. З масиву, з іншого боку, це не збирається робити копію, і ви будете фактично редагування Сам дуже масив. 

Так один тип роду є вибір роду. Вибір роду працює, починаючи з початок, а потім ітерації знову і знайти найменший елемент. І тоді ви поміняти, що маленький елемент з першою. А потім ви переходите на другий елемент , Знайти наступний за величиною елемент, а потім поміняти, що з Другий елемент в масиві, так як перший елемент вже відсортовані. І так, то ви як і раніше для кожного елементом в процесі виявлення найменших значення і заміни його. 

Бо я дорівнює 0, найперший елемент п мінус 1, ви збираєтеся порівнювати кожен наступний значення після цього і знайти індекс мінімального значення. Як тільки ви знайдете індекс мінімального значення, ви можете поміняти це значення масиву Мінімальна і масив І. 

Інший тип роду, що ви можете реалізувати це бульбашкового сортування. Так бульбашкового сортування перебирає список порівнянні сусідніх елементів і перекачування елементи, які знаходяться в неправильному порядку. І таким чином, найбільший елемент буде пузиритися до кінця. НЕ І список сортується раз не більше елементи були замінені. 

Отже, це два приклади роду алгоритми, які можна реалізувати для програма знахідка. Як тільки ви закінчите роду, і в тебе зроблено пошуку, ви закінчите. Мене звуть Zamyla, і це CS50. 

[Музика грає]