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

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

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

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

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

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

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

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

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

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