ROB BOWDEN: Привіт, я Роб. Як ми використовуємо бінарний пошук? Давайте з'ясуємо. Так, зверніть увагу, що цей пошук ми збираємося реалізувати рекурсивно. Крім того, можна реалізувати бінарний пошук багаторазово, так що якщо ви це зробили, це абсолютно нормально. 

Тепер спочатку, давайте пам'ятати, що Параметри для пошуку призначені для. Тут ми бачимо десяткового значення, яке має бути значення користувач пошук. Ми бачимо масив Int цінності, які це масив, в якому ми пошук значення. І ми бачимо, Int N, який є довжина нашого масиву. 

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

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

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

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

У рекурсивному виклику для пошуку, ми тепер кажуть, що довжина масив середній. Так що, якщо наш масив був розміром 20 і ми Пошук за індексом 10, так як середина 20 розділити на 2, що означає, що ми проходячи 10 як новий довжина нашого масиву. Пам'ятайте, що коли у вас є масив довжиною 10, це означає, що діє елементи знаходяться в індексів від 0 до 9. Так що це саме те, що ми хочемо вказати наш оновлений масив - лівий Масив з середнього елемента. 

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

Знову ж, якщо масив були розміром 20 і ми ділимо на 2, щоб отримати середину, так середина 10, то п мінус середнього збирається дати нам 10, так 10 елементи праворуч від середини. Але у нас є цей мінус 1, так як ми не хочемо, щоб включають саму середину. Так н мінус середній мінус 1 дає нам Загальна кількість елементів праворуч середнього індексу в масиві. 

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

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

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

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

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

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

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

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

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

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

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