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, дзеліцца на 11 лютага. 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 кастрычніка, дзеліцца на 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, дзеліцца на 11 лютага. 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.. 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