>> [Грає музика]
>> ДАГ Lloyd: Гаразд.
Так бінарний пошук є Алгоритм можна використовувати
знайти елемент всередині масиву.
На відміну від лінійного пошуку, він вимагає особливий стан бути виконані заздалегідь,
але це так набагато більш ефективним, якщо ця умова, насправді, зустрілися.
>> Так що ідея тут?
це розділяй і володарюй.
Ми хочемо, щоб зменшити розмір область пошуку на половину кожного часу
Щоб знайти номер адресата.
Це де це умова вступає в гру, хоча.
Ми можемо тільки використовувати можливості усуваючи половини елементів
навіть не дивлячись на їм, якщо масив відсортований.
>> Якщо це повна плутанина, Ми не можемо просто з рук
відкинути половину елементів, так ми не знаємо, що ми відкидаючи.
Але якщо масив відсортований, ми можемо зробити це, тому що ми
знати, що все в залишили, де ми в даний час
повинна бути нижче, ніж значення ми в даний час.
І все до Право, де ми
повинна бути більше, ніж значення ми в даний час дивиться.
>> Так що псевдокод кроки для бінарного пошуку?
Ми повторюємо цей процес до тих пір, масив або, як ми пройти через,
суб масиви, дрібні шматочки вихідний масив, має розмір 0.
Розрахувати середню поточного підобласті.
>> Якщо значення, яке ви шукаєте, в цьому елементі масиву, зупинитися.
Ви їх знайшли.
Це чудово.
В іншому випадку, якщо мета менше, ніж те, що в середині,
так що якщо значення, яке ми шукаємо для менше, ніж те, що ми бачимо,
повторити цей процес ще раз, але змінити кінцеву точку, а не
буття оригінал завершити повний спектр,
щоб бути тільки зліва де ми просто дивилися.
>> Ми знали, що середня була занадто високою, або мета була менше, ніж у середині,
і тому він повинен існувати, якщо він взагалі існує в масиві,
де в лівій частині середини.
І тому ми будемо встановлювати масив місце тільки для лівої
від середньої точки в як новий пункт.
І навпаки, якщо мета більше, ніж те, що в середині,
ми робимо точно такий же процес, але замість цього ми
змінити початкову точку, щоб бути тільки праворуч від середини
ми тільки що вирахували.
І тоді ми починаємо процес знову.
>> Давайте собі це, добре?
Таким чином, є багато всього відбувається, і тут, але от масив з 15 елементів.
І ми збираємося бути відстеження багато більше речей на цей раз.
Таким чином, в лінійному пошуку, ми були тільки піклуючись про мету.
Але цього разу ми хочемо, щоб піклуватися про де ми
починає виглядати, де ми зупинилися, дивлячись,
і те, що середина поточного масиву.
Так от ми йдемо з бінарного пошуку.
Ми досить багато добре йти, вірно?
Я просто хочу, щоб покласти вниз нижче тут безліч індексів.
Це в основному тільки те, що елемент масиву ми говоримо про.
При лінійному пошуку, ми піклуватися, оскільки ми
потрібно знати, скільки елементи ми Перебір,
але ми насправді не хвилює, що елемент в даний час ми дивимося.
У бінарного пошуку, ми робимо.
І так ті просто там трохи керівництва.
>> Таким чином, ми можемо почати, правильно?
Ну, не зовсім.
Пам'ятайте, що я сказав, про довічного пошуку?
Ми не можемо зробити це на несортоване масив або ще,
ми не гарантує, що деякі елементи або значення не
випадкового відкидаються, коли ми просто
вирішили ігнорувати половина масиву.
>> Так крок сам з бінарного пошуку це ви повинні мати впорядкований масив.
І ви можете використовувати будь-який з сортування алгоритми ми говорили про
щоб ви на цю посаду.
Так що тепер, ми в такому становищі, коли ми можемо виконати бінарний пошук.
>> Так давайте повторимо процес крок за кроком, і тримайте
трек, що відбувається, як ми йдемо.
Таким чином, спочатку ми повинні зробити, це розрахувати середина поточного масиву.
Ну, ми сказати, що ми, в першу всі, дивлячись на вартість 19.
Ми намагаємося, щоб знайти номер 19.
Перший елемент цього Масив розташований з індексом нуль,
а останній елемент в цьому Масив розташований за індексі 14.
І так ми будемо називати тих, початок і кінець.
>> Таким чином, ми обчислити середню по додавши 0 плюс 14 поділене на 2;
досить просто середина.
І ми можемо сказати, що середина зараз 7.
Так 15 те, що ми шукаємо?
Ні це не так.
Ми шукаємо 19.
Але ми знаємо, що 19 більше, ніж те, що ми знайшли в середині.
>> Отже, що ми можемо зробити, це змінити початкову точку
щоб бути просто праворуч від середина, і повторити процес знову.
І коли ми це зробимо, ми тепер сказати Новий старт точка розташування масиву 8.
Те, що ми зробили це ефективно ігноруються всі зліва від 15.
Ми ліквідували половину проблеми, і в даний час,
замість того, щоб шукати більше 15 елементів у масиві,
у нас є тільки для пошуку більш 7.
Так 8 є новий старт точка.
14 як і раніше є кінцевою точкою.
>> А тепер, перейдемо це знову.
Ми обчислюємо нове середину.
8 плюс 14 22, ділиться на 2 листопада.
Це те, що ми шукаємо?
Ні це не так.
Ми шукаємо значенням, менше, ніж те, що ми тільки що знайшли.
Так що ми збираємося повторити процес знову.
Ми збираємося змінити кінцеву точку для якраз зліва середини.
Таким чином, новий кінцевий пункт стає 10.
А тепер, ось тільки частина масив, ми повинні розібратися в.
Таким чином, ми вже усунені 12 з 15 елементів.
Ми знаємо, що, якщо 19 існує в масиві, це
повинен існувати десь між елементом № 8 та № 10 елемент.
>> Таким чином, ми обчислюємо нове середину знову.
8 плюс 18 жовтня, ділиться на 2 9.
І в цьому випадку, дивіться, мета в середині.
Ми знайшли саме те, що ми шукаємо.
Ми можемо зупинити.
Ми успішно завершили двійковий пошук.
Добре.
Отже, ми знаємо цей алгоритм працює, якщо мета
десь всередині масиву.
Чи означає це працювати, якщо алгоритм мета не в масиві?
Ну, давайте почнемо її знову, і цього разу,
давайте подивимося на елемент 16, які візуально видно,
ніде не існує в масиві.
>> Початкова точка знову 0.
Кінцева точка знову 14.
Такі показники першого і Останні елементи масиву. Повний
І ми будемо йти через процес ми тільки пішов через раз, намагаючись знайти 16,
навіть якщо візуально, ми можемо вже сказати, що він не збирається бути там.
Ми просто хочемо, щоб переконатися, що цей алгоритм буде, насправді, досі працюють в якійсь мірі
і не просто залишити нам застряг у нескінченному циклі.
>> Так що крок першим?
Розрахувати середню поточного масиву.
Що середина поточного масиву?
Ну, це 7, вірно?
14 плюс 0 розділити на 2, 7.
15 те, що ми шукаємо?
Немає.
Це досить близько, але ми шукаємо для значення трохи більше, ніж це.
>> Отже, ми знаємо, що це буде же не бути ніде зліва 15.
Цільове більше що в середині.
І тому ми встановлюємо нову початкову точку для якраз праворуч від середини.
Середина нині 7, так скажімо, нову початкову точку 8.
І те, що ми фактично зробити ще раз ігнорується
вся ліва половина масиву.
>> Тепер ми повторюємо обробляти ще раз.
Розрахувати нову середню.
8 плюс 14 22, ділиться на 2 листопада.
23 те, що ми шукаємо?
На жаль, немає.
Ми шукаємо значення що менше, ніж 23.
І тому в даному випадку, ми збираємося змінити кінцеву точку, щоб бути просто
зліва від поточного середині.
В даний час середня точка 11, і тому ми задамо нову кінцеву точку
наступного разу ми йдемо через цей процес до 10.
>> Знову ж таки, ми йдемо через процес знову.
Розрахувати середню.
8 плюс 10 ділиться на 2 9.
Є 19, що ми шукаємо?
На жаль, немає.
Ми все ще шукаємо число менше.
Таким чином, ми змінити кінцеву точку цього разу бути просто зліва середини.
Середина нині 9, так що кінцева точка буде 8.
І тепер, ми просто шукаємо в одному масиві елемента.
>> Що середина цього масиву?
Ну, він починається в 8, це закінчується в 8, середина 8.
Це те, що ми шукаємо?
Ми шукаємо 17?
Ні, ми шукаємо 16.
Так що, якщо він існує в масиві, вона повинна десь існувати
ліворуч, де ми в даний час.
Так що ми будемо робити?
Ну, ми встановити кінцеву точку, щоб бути просто зліва від поточного середині.
Таким чином, ми змінити кінцеву точку до 7.
Ви бачите, що тільки тут сталося, правда?
Подивіться тут.
>> Почати зараз більше, ніж кінець.
Фактично, два кінця з нашого масиву перейшли,
і початкова точка знаходиться Тепер після того, як в кінцевій точці.
Ну, це не ніякого сенсу, чи не так?
Так що тепер, що ми можемо сказати, що ми є суб масив розміром 0.
І як тільки ми дісталися до Ця точка зору, ми можемо в даний час
гарантувати, що елемент 16 не існує в масиві,
тому початкової точки і кінцева точка перейшли.
І таким чином це не там.
Тепер, зверніть увагу, що це трохи відрізняється від точки початку і закінчення
Суть в тому, те ж саме.
Якби ми були дивлячись на 17, це було б
був в масиві, і точки старту і кінцева точка цього останній ітерації
перш ніж ці точки перетинаються, ми б знайшли 17 там.
Це тільки, коли вони перетинають, що ми можемо гарантувати, що елементи не
існує в масиві.
>> Отже, давайте багато менше кроків, ніж лінійний пошук.
У гіршому випадку, ми мали розділити список елементів п
неодноразово в половині, щоб знайти мету, або тому, що цільовий елемент
буде десь в останній поділ, або він не існує взагалі.
Таким чином, в гіршому випадку, ми повинні розділити на array-- ви знаєте?
Журнал п разів; ми повинні скоротити проблеми
в половині певну кількість разів.
Це число раз є журнал п.
>> Який найкращий сценарій?
Ну, в перший раз ми розрахувати середню,
ми знаходимо, що ми шукаємо.
У всіх попередніх приклади на бінарний пошук
ми щойно закінчилася, якби ми мали шукав елемента 15,
ми виявили, що негайно.
Це було на самому початку.
Це було середина перша спроба розколу
дивізії в бінарний пошук.
>> І так в гіршому так, бінарний пошук працює
в журналі п, що значно краще, ніж лінійний пошук, в гіршому випадку.
У кращому випадку, двійковий Пошук працює омега 1.
Так бінарний пошук багато краще, ніж лінійний пошук,
але вам доводиться мати справу з процесом сортування свій масив, перш ніж ви можете
використовувати силу довічного пошуку.
>> Я Дуг Ллойд.
Це CS 50.