1 00:00:00,000 --> 00:00:03,346 >> [Грає музика] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> ДАГ Lloyd: Гаразд. 4 00:00:06,220 --> 00:00:08,140 Так бінарний пошук є Алгоритм можна використовувати 5 00:00:08,140 --> 00:00:10,530 знайти елемент всередині масиву. 6 00:00:10,530 --> 00:00:14,710 На відміну від лінійного пошуку, він вимагає особливий стан бути виконані заздалегідь, 7 00:00:14,710 --> 00:00:19,020 але це так набагато більш ефективним, якщо ця умова, насправді, зустрілися. 8 00:00:19,020 --> 00:00:20,470 >> Так що ідея тут? 9 00:00:20,470 --> 00:00:21,780 це розділяй і володарюй. 10 00:00:21,780 --> 00:00:25,100 Ми хочемо, щоб зменшити розмір область пошуку на половину кожного часу 11 00:00:25,100 --> 00:00:27,240 Щоб знайти номер адресата. 12 00:00:27,240 --> 00:00:29,520 Це де це умова вступає в гру, хоча. 13 00:00:29,520 --> 00:00:32,740 Ми можемо тільки використовувати можливості усуваючи половини елементів 14 00:00:32,740 --> 00:00:36,070 навіть не дивлячись на їм, якщо масив відсортований. 15 00:00:36,070 --> 00:00:39,200 >> Якщо це повна плутанина, Ми не можемо просто з рук 16 00:00:39,200 --> 00:00:42,870 відкинути половину елементів, так ми не знаємо, що ми відкидаючи. 17 00:00:42,870 --> 00:00:45,624 Але якщо масив відсортований, ми можемо зробити це, тому що ми 18 00:00:45,624 --> 00:00:48,040 знати, що все в залишили, де ми в даний час 19 00:00:48,040 --> 00:00:50,500 повинна бути нижче, ніж значення ми в даний час. 20 00:00:50,500 --> 00:00:52,300 І все до Право, де ми 21 00:00:52,300 --> 00:00:55,040 повинна бути більше, ніж значення ми в даний час дивиться. 22 00:00:55,040 --> 00:00:58,710 >> Так що псевдокод кроки для бінарного пошуку? 23 00:00:58,710 --> 00:01:02,310 Ми повторюємо цей процес до тих пір, масив або, як ми пройти через, 24 00:01:02,310 --> 00:01:07,740 суб масиви, дрібні шматочки вихідний масив, має розмір 0. 25 00:01:07,740 --> 00:01:10,960 Розрахувати середню поточного підобласті. 26 00:01:10,960 --> 00:01:14,460 >> Якщо значення, яке ви шукаєте, в цьому елементі масиву, зупинитися. 27 00:01:14,460 --> 00:01:15,030 Ви їх знайшли. 28 00:01:15,030 --> 00:01:16,550 Це чудово. 29 00:01:16,550 --> 00:01:19,610 В іншому випадку, якщо мета менше, ніж те, що в середині, 30 00:01:19,610 --> 00:01:23,430 так що якщо значення, яке ми шукаємо для менше, ніж те, що ми бачимо, 31 00:01:23,430 --> 00:01:26,780 повторити цей процес ще раз, але змінити кінцеву точку, а не 32 00:01:26,780 --> 00:01:29,300 буття оригінал завершити повний спектр, 33 00:01:29,300 --> 00:01:34,110 щоб бути тільки зліва де ми просто дивилися. 34 00:01:34,110 --> 00:01:38,940 >> Ми знали, що середня була занадто високою, або мета була менше, ніж у середині, 35 00:01:38,940 --> 00:01:42,210 і тому він повинен існувати, якщо він взагалі існує в масиві, 36 00:01:42,210 --> 00:01:44,660 де в лівій частині середини. 37 00:01:44,660 --> 00:01:48,120 І тому ми будемо встановлювати масив місце тільки для лівої 38 00:01:48,120 --> 00:01:51,145 від середньої точки в як новий пункт. 39 00:01:51,145 --> 00:01:53,770 І навпаки, якщо мета більше, ніж те, що в середині, 40 00:01:53,770 --> 00:01:55,750 ми робимо точно такий же процес, але замість цього ми 41 00:01:55,750 --> 00:01:59,520 змінити початкову точку, щоб бути тільки праворуч від середини 42 00:01:59,520 --> 00:02:00,680 ми тільки що вирахували. 43 00:02:00,680 --> 00:02:03,220 І тоді ми починаємо процес знову. 44 00:02:03,220 --> 00:02:05,220 >> Давайте собі це, добре? 45 00:02:05,220 --> 00:02:08,620 Таким чином, є багато всього відбувається, і тут, але от масив з 15 елементів. 46 00:02:08,620 --> 00:02:11,400 І ми збираємося бути відстеження багато більше речей на цей раз. 47 00:02:11,400 --> 00:02:13,870 Таким чином, в лінійному пошуку, ми були тільки піклуючись про мету. 48 00:02:13,870 --> 00:02:15,869 Але цього разу ми хочемо, щоб піклуватися про де ми 49 00:02:15,869 --> 00:02:18,480 починає виглядати, де ми зупинилися, дивлячись, 50 00:02:18,480 --> 00:02:21,876 і те, що середина поточного масиву. 51 00:02:21,876 --> 00:02:23,250 Так от ми йдемо з бінарного пошуку. 52 00:02:23,250 --> 00:02:25,290 Ми досить багато добре йти, вірно? 53 00:02:25,290 --> 00:02:28,650 Я просто хочу, щоб покласти вниз нижче тут безліч індексів. 54 00:02:28,650 --> 00:02:32,430 Це в основному тільки те, що елемент масиву ми говоримо про. 55 00:02:32,430 --> 00:02:34,500 При лінійному пошуку, ми піклуватися, оскільки ми 56 00:02:34,500 --> 00:02:36,800 потрібно знати, скільки елементи ми Перебір, 57 00:02:36,800 --> 00:02:40,010 але ми насправді не хвилює, що елемент в даний час ми дивимося. 58 00:02:40,010 --> 00:02:41,014 У бінарного пошуку, ми робимо. 59 00:02:41,014 --> 00:02:42,930 І так ті просто там трохи керівництва. 60 00:02:42,930 --> 00:02:44,910 >> Таким чином, ми можемо почати, правильно? 61 00:02:44,910 --> 00:02:46,240 Ну, не зовсім. 62 00:02:46,240 --> 00:02:48,160 Пам'ятайте, що я сказав, про довічного пошуку? 63 00:02:48,160 --> 00:02:50,955 Ми не можемо зробити це на несортоване масив або ще, 64 00:02:50,955 --> 00:02:55,820 ми не гарантує, що деякі елементи або значення не 65 00:02:55,820 --> 00:02:57,650 випадкового відкидаються, коли ми просто 66 00:02:57,650 --> 00:02:59,920 вирішили ігнорувати половина масиву. 67 00:02:59,920 --> 00:03:02,574 >> Так крок сам з бінарного пошуку це ви повинні мати впорядкований масив. 68 00:03:02,574 --> 00:03:05,240 І ви можете використовувати будь-який з сортування алгоритми ми говорили про 69 00:03:05,240 --> 00:03:06,700 щоб ви на цю посаду. 70 00:03:06,700 --> 00:03:10,370 Так що тепер, ми в такому становищі, коли ми можемо виконати бінарний пошук. 71 00:03:10,370 --> 00:03:12,560 >> Так давайте повторимо процес крок за кроком, і тримайте 72 00:03:12,560 --> 00:03:14,830 трек, що відбувається, як ми йдемо. 73 00:03:14,830 --> 00:03:17,980 Таким чином, спочатку ми повинні зробити, це розрахувати середина поточного масиву. 74 00:03:17,980 --> 00:03:20,620 Ну, ми сказати, що ми, в першу всі, дивлячись на вартість 19. 75 00:03:20,620 --> 00:03:22,290 Ми намагаємося, щоб знайти номер 19. 76 00:03:22,290 --> 00:03:25,380 Перший елемент цього Масив розташований з індексом нуль, 77 00:03:25,380 --> 00:03:28,880 а останній елемент в цьому Масив розташований за індексі 14. 78 00:03:28,880 --> 00:03:31,430 І так ми будемо називати тих, початок і кінець. 79 00:03:31,430 --> 00:03:35,387 >> Таким чином, ми обчислити середню по додавши 0 плюс 14 поділене на 2; 80 00:03:35,387 --> 00:03:36,720 досить просто середина. 81 00:03:36,720 --> 00:03:40,190 І ми можемо сказати, що середина зараз 7. 82 00:03:40,190 --> 00:03:43,370 Так 15 те, що ми шукаємо? 83 00:03:43,370 --> 00:03:43,940 Ні це не так. 84 00:03:43,940 --> 00:03:45,270 Ми шукаємо 19. 85 00:03:45,270 --> 00:03:49,400 Але ми знаємо, що 19 більше, ніж те, що ми знайшли в середині. 86 00:03:49,400 --> 00:03:52,470 >> Отже, що ми можемо зробити, це змінити початкову точку 87 00:03:52,470 --> 00:03:57,280 щоб бути просто праворуч від середина, і повторити процес знову. 88 00:03:57,280 --> 00:04:01,690 І коли ми це зробимо, ми тепер сказати Новий старт точка розташування масиву 8. 89 00:04:01,690 --> 00:04:07,220 Те, що ми зробили це ефективно ігноруються всі зліва від 15. 90 00:04:07,220 --> 00:04:09,570 Ми ліквідували половину проблеми, і в даний час, 91 00:04:09,570 --> 00:04:13,510 замість того, щоб шукати більше 15 елементів у масиві, 92 00:04:13,510 --> 00:04:15,610 у нас є тільки для пошуку більш 7. 93 00:04:15,610 --> 00:04:17,706 Так 8 є новий старт точка. 94 00:04:17,706 --> 00:04:19,600 14 як і раніше є кінцевою точкою. 95 00:04:19,600 --> 00:04:21,430 >> А тепер, перейдемо це знову. 96 00:04:21,430 --> 00:04:22,810 Ми обчислюємо нове середину. 97 00:04:22,810 --> 00:04:27,130 8 плюс 14 22, ділиться на 2 листопада. 98 00:04:27,130 --> 00:04:28,660 Це те, що ми шукаємо? 99 00:04:28,660 --> 00:04:30,110 Ні це не так. 100 00:04:30,110 --> 00:04:32,930 Ми шукаємо значенням, менше, ніж те, що ми тільки що знайшли. 101 00:04:32,930 --> 00:04:34,721 Так що ми збираємося повторити процес знову. 102 00:04:34,721 --> 00:04:38,280 Ми збираємося змінити кінцеву точку для якраз зліва середини. 103 00:04:38,280 --> 00:04:41,800 Таким чином, новий кінцевий пункт стає 10. 104 00:04:41,800 --> 00:04:44,780 А тепер, ось тільки частина масив, ми повинні розібратися в. 105 00:04:44,780 --> 00:04:48,460 Таким чином, ми вже усунені 12 з 15 елементів. 106 00:04:48,460 --> 00:04:51,550 Ми знаємо, що, якщо 19 існує в масиві, це 107 00:04:51,550 --> 00:04:57,210 повинен існувати десь між елементом № 8 та № 10 елемент. 108 00:04:57,210 --> 00:04:59,400 >> Таким чином, ми обчислюємо нове середину знову. 109 00:04:59,400 --> 00:05:02,900 8 плюс 18 жовтня, ділиться на 2 9. 110 00:05:02,900 --> 00:05:05,074 І в цьому випадку, дивіться, мета в середині. 111 00:05:05,074 --> 00:05:06,740 Ми знайшли саме те, що ми шукаємо. 112 00:05:06,740 --> 00:05:07,780 Ми можемо зупинити. 113 00:05:07,780 --> 00:05:10,561 Ми успішно завершили двійковий пошук. 114 00:05:10,561 --> 00:05:11,060 Добре. 115 00:05:11,060 --> 00:05:13,930 Отже, ми знаємо цей алгоритм працює, якщо мета 116 00:05:13,930 --> 00:05:16,070 десь всередині масиву. 117 00:05:16,070 --> 00:05:19,060 Чи означає це працювати, якщо алгоритм мета не в масиві? 118 00:05:19,060 --> 00:05:20,810 Ну, давайте почнемо її знову, і цього разу, 119 00:05:20,810 --> 00:05:23,380 давайте подивимося на елемент 16, які візуально видно, 120 00:05:23,380 --> 00:05:25,620 ніде не існує в масиві. 121 00:05:25,620 --> 00:05:27,110 >> Початкова точка знову 0. 122 00:05:27,110 --> 00:05:28,590 Кінцева точка знову 14. 123 00:05:28,590 --> 00:05:32,490 Такі показники першого і Останні елементи масиву. Повний 124 00:05:32,490 --> 00:05:36,057 І ми будемо йти через процес ми тільки пішов через раз, намагаючись знайти 16, 125 00:05:36,057 --> 00:05:39,140 навіть якщо візуально, ми можемо вже сказати, що він не збирається бути там. 126 00:05:39,140 --> 00:05:43,450 Ми просто хочемо, щоб переконатися, що цей алгоритм буде, насправді, досі працюють в якійсь мірі 127 00:05:43,450 --> 00:05:46,310 і не просто залишити нам застряг у нескінченному циклі. 128 00:05:46,310 --> 00:05:48,190 >> Так що крок першим? 129 00:05:48,190 --> 00:05:50,230 Розрахувати середню поточного масиву. 130 00:05:50,230 --> 00:05:52,790 Що середина поточного масиву? 131 00:05:52,790 --> 00:05:54,410 Ну, це 7, вірно? 132 00:05:54,410 --> 00:05:57,560 14 плюс 0 розділити на 2, 7. 133 00:05:57,560 --> 00:05:59,280 15 те, що ми шукаємо? 134 00:05:59,280 --> 00:05:59,780 Немає. 135 00:05:59,780 --> 00:06:02,930 Це досить близько, але ми шукаємо для значення трохи більше, ніж це. 136 00:06:02,930 --> 00:06:06,310 >> Отже, ми знаємо, що це буде же не бути ніде зліва 15. 137 00:06:06,310 --> 00:06:08,540 Цільове більше що в середині. 138 00:06:08,540 --> 00:06:12,450 І тому ми встановлюємо нову початкову точку для якраз праворуч від середини. 139 00:06:12,450 --> 00:06:16,130 Середина нині 7, так скажімо, нову початкову точку 8. 140 00:06:16,130 --> 00:06:18,130 І те, що ми фактично зробити ще раз ігнорується 141 00:06:18,130 --> 00:06:21,150 вся ліва половина масиву. 142 00:06:21,150 --> 00:06:23,750 >> Тепер ми повторюємо обробляти ще раз. 143 00:06:23,750 --> 00:06:24,910 Розрахувати нову середню. 144 00:06:24,910 --> 00:06:29,350 8 плюс 14 22, ділиться на 2 листопада. 145 00:06:29,350 --> 00:06:31,060 23 те, що ми шукаємо? 146 00:06:31,060 --> 00:06:31,870 На жаль, немає. 147 00:06:31,870 --> 00:06:34,930 Ми шукаємо значення що менше, ніж 23. 148 00:06:34,930 --> 00:06:37,850 І тому в даному випадку, ми збираємося змінити кінцеву точку, щоб бути просто 149 00:06:37,850 --> 00:06:40,035 зліва від поточного середині. 150 00:06:40,035 --> 00:06:43,440 В даний час середня точка 11, і тому ми задамо нову кінцеву точку 151 00:06:43,440 --> 00:06:46,980 наступного разу ми йдемо через цей процес до 10. 152 00:06:46,980 --> 00:06:48,660 >> Знову ж таки, ми йдемо через процес знову. 153 00:06:48,660 --> 00:06:49,640 Розрахувати середню. 154 00:06:49,640 --> 00:06:53,100 8 плюс 10 ділиться на 2 9. 155 00:06:53,100 --> 00:06:54,750 Є 19, що ми шукаємо? 156 00:06:54,750 --> 00:06:55,500 На жаль, немає. 157 00:06:55,500 --> 00:06:58,050 Ми все ще шукаємо число менше. 158 00:06:58,050 --> 00:07:02,060 Таким чином, ми змінити кінцеву точку цього разу бути просто зліва середини. 159 00:07:02,060 --> 00:07:05,532 Середина нині 9, так що кінцева точка буде 8. 160 00:07:05,532 --> 00:07:07,920 І тепер, ми просто шукаємо в одному масиві елемента. 161 00:07:07,920 --> 00:07:10,250 >> Що середина цього масиву? 162 00:07:10,250 --> 00:07:13,459 Ну, він починається в 8, це закінчується в 8, середина 8. 163 00:07:13,459 --> 00:07:14,750 Це те, що ми шукаємо? 164 00:07:14,750 --> 00:07:16,339 Ми шукаємо 17? 165 00:07:16,339 --> 00:07:17,380 Ні, ми шукаємо 16. 166 00:07:17,380 --> 00:07:20,160 Так що, якщо він існує в масиві, вона повинна десь існувати 167 00:07:20,160 --> 00:07:21,935 ліворуч, де ми в даний час. 168 00:07:21,935 --> 00:07:23,060 Так що ми будемо робити? 169 00:07:23,060 --> 00:07:26,610 Ну, ми встановити кінцеву точку, щоб бути просто зліва від поточного середині. 170 00:07:26,610 --> 00:07:29,055 Таким чином, ми змінити кінцеву точку до 7. 171 00:07:29,055 --> 00:07:32,120 Ви бачите, що тільки тут сталося, правда? 172 00:07:32,120 --> 00:07:33,370 Подивіться тут. 173 00:07:33,370 --> 00:07:35,970 >> Почати зараз більше, ніж кінець. 174 00:07:35,970 --> 00:07:39,620 Фактично, два кінця з нашого масиву перейшли, 175 00:07:39,620 --> 00:07:42,252 і початкова точка знаходиться Тепер після того, як в кінцевій точці. 176 00:07:42,252 --> 00:07:43,960 Ну, це не ніякого сенсу, чи не так? 177 00:07:43,960 --> 00:07:47,960 Так що тепер, що ми можемо сказати, що ми є суб масив розміром 0. 178 00:07:47,960 --> 00:07:50,110 І як тільки ми дісталися до Ця точка зору, ми можемо в даний час 179 00:07:50,110 --> 00:07:53,940 гарантувати, що елемент 16 не існує в масиві, 180 00:07:53,940 --> 00:07:56,280 тому початкової точки і кінцева точка перейшли. 181 00:07:56,280 --> 00:07:58,340 І таким чином це не там. 182 00:07:58,340 --> 00:08:01,340 Тепер, зверніть увагу, що це трохи відрізняється від точки початку і закінчення 183 00:08:01,340 --> 00:08:02,900 Суть в тому, те ж саме. 184 00:08:02,900 --> 00:08:05,030 Якби ми були дивлячись на 17, це було б 185 00:08:05,030 --> 00:08:08,870 був в масиві, і точки старту і кінцева точка цього останній ітерації 186 00:08:08,870 --> 00:08:11,820 перш ніж ці точки перетинаються, ми б знайшли 17 там. 187 00:08:11,820 --> 00:08:15,510 Це тільки, коли вони перетинають, що ми можемо гарантувати, що елементи не 188 00:08:15,510 --> 00:08:17,180 існує в масиві. 189 00:08:17,180 --> 00:08:20,260 >> Отже, давайте багато менше кроків, ніж лінійний пошук. 190 00:08:20,260 --> 00:08:23,250 У гіршому випадку, ми мали розділити список елементів п 191 00:08:23,250 --> 00:08:27,770 неодноразово в половині, щоб знайти мету, або тому, що цільовий елемент 192 00:08:27,770 --> 00:08:33,110 буде десь в останній поділ, або він не існує взагалі. 193 00:08:33,110 --> 00:08:37,830 Таким чином, в гіршому випадку, ми повинні розділити на array-- ви знаєте? 194 00:08:37,830 --> 00:08:40,510 Журнал п разів; ми повинні скоротити проблеми 195 00:08:40,510 --> 00:08:42,610 в половині певну кількість разів. 196 00:08:42,610 --> 00:08:45,160 Це число раз є журнал п. 197 00:08:45,160 --> 00:08:46,510 >> Який найкращий сценарій? 198 00:08:46,510 --> 00:08:48,899 Ну, в перший раз ми розрахувати середню, 199 00:08:48,899 --> 00:08:50,190 ми знаходимо, що ми шукаємо. 200 00:08:50,190 --> 00:08:52,150 У всіх попередніх приклади на бінарний пошук 201 00:08:52,150 --> 00:08:55,489 ми щойно закінчилася, якби ми мали шукав елемента 15, 202 00:08:55,489 --> 00:08:57,030 ми виявили, що негайно. 203 00:08:57,030 --> 00:08:58,321 Це було на самому початку. 204 00:08:58,321 --> 00:09:01,200 Це було середина перша спроба розколу 205 00:09:01,200 --> 00:09:03,950 дивізії в бінарний пошук. 206 00:09:03,950 --> 00:09:06,350 >> І так в гіршому так, бінарний пошук працює 207 00:09:06,350 --> 00:09:11,580 в журналі п, що значно краще, ніж лінійний пошук, в гіршому випадку. 208 00:09:11,580 --> 00:09:16,210 У кращому випадку, двійковий Пошук працює омега 1. 209 00:09:16,210 --> 00:09:18,990 Так бінарний пошук багато краще, ніж лінійний пошук, 210 00:09:18,990 --> 00:09:23,270 але вам доводиться мати справу з процесом сортування свій масив, перш ніж ви можете 211 00:09:23,270 --> 00:09:26,140 використовувати силу довічного пошуку. 212 00:09:26,140 --> 00:09:27,130 >> Я Дуг Ллойд. 213 00:09:27,130 --> 00:09:29,470 Це CS 50. 214 00:09:29,470 --> 00:09:31,070