1 00:00:00,000 --> 00:00:03,346 >> [Přehrávání hudby] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG LLOYD: Dobře. 4 00:00:06,220 --> 00:00:08,140 Takže binární vyhledávání je Algoritmus můžeme použít 5 00:00:08,140 --> 00:00:10,530 najít prvek uvnitř pole. 6 00:00:10,530 --> 00:00:14,710 Na rozdíl od lineární hledání, to vyžaduje Zvláštní podmínka být splněna předem, 7 00:00:14,710 --> 00:00:19,020 ale je to mnohem účinnější, pokud tato podmínka je, ve skutečnosti, se setkal. 8 00:00:19,020 --> 00:00:20,470 >> Takže to, co je tady nápad? 9 00:00:20,470 --> 00:00:21,780 je to rozděl a panuj. 10 00:00:21,780 --> 00:00:25,100 Chceme snížit velikost oblast hledání o polovinu každý čas 11 00:00:25,100 --> 00:00:27,240 s cílem nalézt cílové číslo. 12 00:00:27,240 --> 00:00:29,520 To je místo, kde tato podmínka přichází do hry, ačkoli. 13 00:00:29,520 --> 00:00:32,740 Můžeme využít pouze sílu odstranění poloviny prvků 14 00:00:32,740 --> 00:00:36,070 aniž by při pohledu na je v případě, že pole se třídí. 15 00:00:36,070 --> 00:00:39,200 >> Pokud je to úplný mix up, Nemůžeme jen tak z ruky 16 00:00:39,200 --> 00:00:42,870 zbavit polovina prvků, protože nevíme, co jsme vyřazení. 17 00:00:42,870 --> 00:00:45,624 Ale v případě, že pole je řazen, můžeme to udělat, protože jsme 18 00:00:45,624 --> 00:00:48,040 vím, že všechno, co k vlevo, kde jsme v současné době jsou 19 00:00:48,040 --> 00:00:50,500 musí být nižší, než je Hodnota jsme v současné době. 20 00:00:50,500 --> 00:00:52,300 A vše, co k právo na to, kde jsme 21 00:00:52,300 --> 00:00:55,040 musí být větší než hodnota jsme v současné době při pohledu na. 22 00:00:55,040 --> 00:00:58,710 >> Takže co je pseudokód kroky pro binární vyhledávání? 23 00:00:58,710 --> 00:01:02,310 Tento postup opakujeme, dokud nebude pole nebo, jak budeme postupovat přes, 24 00:01:02,310 --> 00:01:07,740 podsouborům, menší kusy původní pole je velikosti 0. 25 00:01:07,740 --> 00:01:10,960 Vypočtěte polovinu aktuálního podsouboru. 26 00:01:10,960 --> 00:01:14,460 >> Pokud je hodnota hledáte, je v tomto prvku pole, zastavit. 27 00:01:14,460 --> 00:01:15,030 Našel jsi to. 28 00:01:15,030 --> 00:01:16,550 To je skvělé. 29 00:01:16,550 --> 00:01:19,610 Jinak, pokud je cíl méně než to, co je ve středu, 30 00:01:19,610 --> 00:01:23,430 takže pokud hodnoty díváme pro nižší, než to, co vidíme, 31 00:01:23,430 --> 00:01:26,780 tento proces opakovat, ale změnit koncový bod, místo toho 32 00:01:26,780 --> 00:01:29,300 z toho, že původní dokončit celou řadou, 33 00:01:29,300 --> 00:01:34,110 být jen na levé straně kde jsme se jen podíval. 34 00:01:34,110 --> 00:01:38,940 >> Věděli jsme, že prostřední byla příliš vysoká, nebo cílovou byl menší, než ve středu, 35 00:01:38,940 --> 00:01:42,210 a tak, že musí existovat, je-li to vůbec existuje, v poli, 36 00:01:42,210 --> 00:01:44,660 někde na levé straně středového bodu. 37 00:01:44,660 --> 00:01:48,120 A tak jsme si nastavit pole poloha jen na levé straně 38 00:01:48,120 --> 00:01:51,145 midpoint jako nového koncového bodu. 39 00:01:51,145 --> 00:01:53,770 Naopak, pokud je cíl větší, než to, co je ve středu, 40 00:01:53,770 --> 00:01:55,750 uděláme přesně stejný proces, ale místo toho 41 00:01:55,750 --> 00:01:59,520 změnit počáteční bod, aby jen na pravé straně středu 42 00:01:59,520 --> 00:02:00,680 jsme prostě počítat. 43 00:02:00,680 --> 00:02:03,220 A pak jsme se znovu začít proces. 44 00:02:03,220 --> 00:02:05,220 >> Pojďme si představit to, OK? 45 00:02:05,220 --> 00:02:08,620 Takže je tu spousta děje, a na tu, ale tady je řada z 15 elementů. 46 00:02:08,620 --> 00:02:11,400 A budeme se sledování o mnohem víc věcí tentokrát. 47 00:02:11,400 --> 00:02:13,870 Takže lineární hledání, my jsme byli jen se starat o cíl. 48 00:02:13,870 --> 00:02:15,869 Ale tentokrát chceme péče o tom, kde jsme 49 00:02:15,869 --> 00:02:18,480 začíná vypadat, kde zastavujeme hledáte, 50 00:02:18,480 --> 00:02:21,876 a co je na střed aktuálního pole. 51 00:02:21,876 --> 00:02:23,250 Tak jdeme na to s binární vyhledávání. 52 00:02:23,250 --> 00:02:25,290 Jsme skoro dobré jít, ne? 53 00:02:25,290 --> 00:02:28,650 Já jsem prostě jít dát dolů níže zde množina indexů. 54 00:02:28,650 --> 00:02:32,430 To je v podstatě to, co právě element matice mluvíme. 55 00:02:32,430 --> 00:02:34,500 S lineární hledání, my péče, neboť my 56 00:02:34,500 --> 00:02:36,800 Potřebujeme vědět, kolik prvky, my iterace přes, 57 00:02:36,800 --> 00:02:40,010 ale nemáme vlastně jedno, co element jsme v současné době při pohledu na. 58 00:02:40,010 --> 00:02:41,014 V binární hledání, co děláme. 59 00:02:41,014 --> 00:02:42,930 A tak to jsou jen tam jako malý průvodce. 60 00:02:42,930 --> 00:02:44,910 >> Takže můžeme začít, ne? 61 00:02:44,910 --> 00:02:46,240 No, ne tak docela. 62 00:02:46,240 --> 00:02:48,160 Vzpomeň si, co jsem řekl, o binárního vyhledávání? 63 00:02:48,160 --> 00:02:50,955 Nemůžeme to udělat na netříděný pole nebo jinak, 64 00:02:50,955 --> 00:02:55,820 nejsme zaručit, že určité prvky nebo hodnoty nejsou 65 00:02:55,820 --> 00:02:57,650 náhodnému vypustí, když jsme právě 66 00:02:57,650 --> 00:02:59,920 rozhodnout ignorovat polovinu pole. 67 00:02:59,920 --> 00:03:02,574 >> Takže první krok s binární vyhledávání je musíte mít seřazené pole. 68 00:03:02,574 --> 00:03:05,240 A můžete použít některý z třídění algoritmy jsme mluvili o 69 00:03:05,240 --> 00:03:06,700 abyste se dostali do této pozice. 70 00:03:06,700 --> 00:03:10,370 Takže teď, jsme v pozici, kdy můžeme provádět binární vyhledávání. 71 00:03:10,370 --> 00:03:12,560 >> Takže pojďme proces opakovat krok za krokem a držet 72 00:03:12,560 --> 00:03:14,830 sledovat, co se děje, jak jsme jít. 73 00:03:14,830 --> 00:03:17,980 Takže nejprve musíme udělat, je výpočet střed ze stávajícího pole. 74 00:03:17,980 --> 00:03:20,620 No, budeme se říct, že jsme v první řadě všichni, hledá pro hodnotu 19. 75 00:03:20,620 --> 00:03:22,290 Snažíme se najít číslo 19. 76 00:03:22,290 --> 00:03:25,380 Prvním prvkem této pole je umístěn na indexu nula, 77 00:03:25,380 --> 00:03:28,880 a poslední prvek této pole je umístěn na indexu 14. 78 00:03:28,880 --> 00:03:31,430 A tak budeme říkat ty začátek a konec. 79 00:03:31,430 --> 00:03:35,387 >> Takže jsme vypočítat střed strany přidáním 0 a navíc 14 děleno 2; 80 00:03:35,387 --> 00:03:36,720 docela jednoduché střed. 81 00:03:36,720 --> 00:03:40,190 A můžeme říci, že střed je nyní 7. 82 00:03:40,190 --> 00:03:43,370 Takže je 15 to, co hledáme? 83 00:03:43,370 --> 00:03:43,940 Ne, to není. 84 00:03:43,940 --> 00:03:45,270 Hledáme 19. 85 00:03:45,270 --> 00:03:49,400 Ale my víme, že 19 je větší než to, co jsme našli ve středu. 86 00:03:49,400 --> 00:03:52,470 >> Takže to, co můžeme udělat, je změnit počáteční bod 87 00:03:52,470 --> 00:03:57,280 být jen napravo od střed, a znovu proces opakovat. 88 00:03:57,280 --> 00:04:01,690 A když to uděláme, můžeme nyní říci, Nový začátek bod je umístění pole 8. 89 00:04:01,690 --> 00:04:07,220 To, co jsme skutečně udělali, je ignoroval vše na levé straně 15. 90 00:04:07,220 --> 00:04:09,570 Odstranili jsme polovinu problému, a teď, 91 00:04:09,570 --> 00:04:13,510 místo toho, aby musel vyhledávat více než 15 prvků v našem poli, 92 00:04:13,510 --> 00:04:15,610 máme jen hledat přes 7. 93 00:04:15,610 --> 00:04:17,706 Takže 8 je nový výchozí bod. 94 00:04:17,706 --> 00:04:19,600 14 je stále koncový bod. 95 00:04:19,600 --> 00:04:21,430 >> A teď jsme se projít znovu. 96 00:04:21,430 --> 00:04:22,810 Počítáme nový střed. 97 00:04:22,810 --> 00:04:27,130 8 a 14, je 22, děleno 2, je 11. 98 00:04:27,130 --> 00:04:28,660 Je to to, co hledáme? 99 00:04:28,660 --> 00:04:30,110 Ne, to není. 100 00:04:30,110 --> 00:04:32,930 Hledáme hodnotu, která je méně, než to, co jsme našli. 101 00:04:32,930 --> 00:04:34,721 Takže budeme opakovat opět proces. 102 00:04:34,721 --> 00:04:38,280 Chystáme se změnit koncový bod na být jen na levé straně středu. 103 00:04:38,280 --> 00:04:41,800 Takže nový koncový bod se stane 10. 104 00:04:41,800 --> 00:04:44,780 A teď, to je jen část pole musíme uspořádat. 105 00:04:44,780 --> 00:04:48,460 Takže jsme nyní odstraněny 12 z 15 prvků. 106 00:04:48,460 --> 00:04:51,550 Víme, že v případě 19 existuje v poli, to 107 00:04:51,550 --> 00:04:57,210 musí existovat někde mezi prvkem číslo 8 a prvek číslo 10. 108 00:04:57,210 --> 00:04:59,400 >> Takže jsme vypočítat nový střed znovu. 109 00:04:59,400 --> 00:05:02,900 8 a 10, je 18, děleno 2 je 9. 110 00:05:02,900 --> 00:05:05,074 A v tomto případě, podívejte se Cílem je u středu. 111 00:05:05,074 --> 00:05:06,740 Našli jsme přesně to, co hledáme. 112 00:05:06,740 --> 00:05:07,780 Můžeme se zastavit. 113 00:05:07,780 --> 00:05:10,561 Úspěšně jsme dokončili binární vyhledávání. 114 00:05:10,561 --> 00:05:11,060 Dobře. 115 00:05:11,060 --> 00:05:13,930 Takže víme, tento algoritmus funguje, pokud je cíl 116 00:05:13,930 --> 00:05:16,070 někde uvnitř matice. 117 00:05:16,070 --> 00:05:19,060 Má tento algoritmus pracovat, pokud cíl není v poli? 118 00:05:19,060 --> 00:05:20,810 No, začněme to znovu, a tentokrát, 119 00:05:20,810 --> 00:05:23,380 podívejme se i na prvku 16, který vizuálně vidíme 120 00:05:23,380 --> 00:05:25,620 neexistuje nikde v matici. 121 00:05:25,620 --> 00:05:27,110 >> Počáteční bod je opět 0. 122 00:05:27,110 --> 00:05:28,590 Konečný bod je opět 14. 123 00:05:28,590 --> 00:05:32,490 Ti, kteří jsou indexy první a poslední prvky kompletního pole. 124 00:05:32,490 --> 00:05:36,057 A půjdeme přes proces jsme právě Znovu prošel a snažil se najít 16, 125 00:05:36,057 --> 00:05:39,140 i když vizuálně, můžeme již říct, že to nebude tam. 126 00:05:39,140 --> 00:05:43,450 Chceme jen, aby se ujistil, tento algoritmus bude ve skutečnosti, stále pracovat určitým způsobem 127 00:05:43,450 --> 00:05:46,310 a ne jen opustit nás uvízl v nekonečné smyčce. 128 00:05:46,310 --> 00:05:48,190 >> Takže to, co je první krok? 129 00:05:48,190 --> 00:05:50,230 Vypočtěte polovinu aktuálního pole. 130 00:05:50,230 --> 00:05:52,790 Co je to střed současné pole? 131 00:05:52,790 --> 00:05:54,410 No, je to 7, ne? 132 00:05:54,410 --> 00:05:57,560 14 a 0 děleno 2 je 7. 133 00:05:57,560 --> 00:05:59,280 Je 15 to, co hledáme? 134 00:05:59,280 --> 00:05:59,780 Ne. 135 00:05:59,780 --> 00:06:02,930 Je to docela blízko, ale my hledáme pro hodnotu o něco větší, než je. 136 00:06:02,930 --> 00:06:06,310 >> Takže víme, že to bude být nikde na levé straně 15. 137 00:06:06,310 --> 00:06:08,540 Cílem je větší než co je v středu. 138 00:06:08,540 --> 00:06:12,450 A tak jsme si stanovili nový počáteční bod na být jen vpravo od středu. 139 00:06:12,450 --> 00:06:16,130 Střed je v současné době 7, takže řekněme, že nový začátek bod 8. 140 00:06:16,130 --> 00:06:18,130 A to, co jsme skutečně jsem opět udělal je ignorován 141 00:06:18,130 --> 00:06:21,150 celá levá polovina matice. 142 00:06:21,150 --> 00:06:23,750 >> Nyní jsme opakovat zpracovat ještě jednou. 143 00:06:23,750 --> 00:06:24,910 Vypočítejte nový střed. 144 00:06:24,910 --> 00:06:29,350 8 a 14, je 22, děleno 2, je 11. 145 00:06:29,350 --> 00:06:31,060 Je 23 to, co hledáme? 146 00:06:31,060 --> 00:06:31,870 Bohužel ne. 147 00:06:31,870 --> 00:06:34,930 Hledáme hodnotu která je menší než 23. 148 00:06:34,930 --> 00:06:37,850 A tak v tomto případě, jdeme změnit koncový bod být spravedlivý 149 00:06:37,850 --> 00:06:40,035 nalevo od aktuálního středového bodu. 150 00:06:40,035 --> 00:06:43,440 Současný střed je 11, a takže budeme nastavit nový koncový bod 151 00:06:43,440 --> 00:06:46,980 pro příště jdeme v tomto procesu až 10. 152 00:06:46,980 --> 00:06:48,660 >> Opět jsme projít procesem znovu. 153 00:06:48,660 --> 00:06:49,640 Vypočítejte střed. 154 00:06:49,640 --> 00:06:53,100 8 a 10 děleno 2 je 9. 155 00:06:53,100 --> 00:06:54,750 Je 19 to, co hledáme? 156 00:06:54,750 --> 00:06:55,500 Bohužel ne. 157 00:06:55,500 --> 00:06:58,050 Stále hledáme číslo menší, než je. 158 00:06:58,050 --> 00:07:02,060 Takže budeme měnit koncového bodu, tentokrát být jen na levé straně od středu. 159 00:07:02,060 --> 00:07:05,532 Střed je v současné době 9, takže koncový bod bude 8. 160 00:07:05,532 --> 00:07:07,920 A teď, my jsme jen se dívá v jednom prvku pole. 161 00:07:07,920 --> 00:07:10,250 >> Co je střed tohoto pole? 162 00:07:10,250 --> 00:07:13,459 No, to začíná v 8, je končí v 8, střed je 8. 163 00:07:13,459 --> 00:07:14,750 Je to to, co hledáme? 164 00:07:14,750 --> 00:07:16,339 Hledáme 17? 165 00:07:16,339 --> 00:07:17,380 Ne, my hledáme pro 16. 166 00:07:17,380 --> 00:07:20,160 Takže pokud existuje v poli, že musí existovat někde 167 00:07:20,160 --> 00:07:21,935 na levé straně, kde jsou v současné době. 168 00:07:21,935 --> 00:07:23,060 Tak co budeme dělat? 169 00:07:23,060 --> 00:07:26,610 No, budeme nastavení koncového bodu, aby jen nalevo od aktuálního středového bodu. 170 00:07:26,610 --> 00:07:29,055 Takže budeme-li změnit koncový bod až 7. 171 00:07:29,055 --> 00:07:32,120 Vidíte, co se právě tady stalo, i když? 172 00:07:32,120 --> 00:07:33,370 Podívejte se tady. 173 00:07:33,370 --> 00:07:35,970 >> Start je nyní větší než konec. 174 00:07:35,970 --> 00:07:39,620 Účinně, jsou oba konce z naší nabídku překročily, 175 00:07:39,620 --> 00:07:42,252 a počáteční bod je Nyní po koncový bod. 176 00:07:42,252 --> 00:07:43,960 No, to není nějaký smysl, že jo? 177 00:07:43,960 --> 00:07:47,960 Takže teď, co můžeme říci, je, že jsme mají dílčí pole velikosti 0. 178 00:07:47,960 --> 00:07:50,110 A jakmile jsme dostali do tento bod, můžeme nyní 179 00:07:50,110 --> 00:07:53,940 zaručit, že prvek 16 neexistuje v matici, 180 00:07:53,940 --> 00:07:56,280 proto, že výchozí bod a koncový bod, které překročily. 181 00:07:56,280 --> 00:07:58,340 A tak je to tam není. 182 00:07:58,340 --> 00:08:01,340 Teď, všimněte si, že je to poněkud liší od počátečního bodu a na konci 183 00:08:01,340 --> 00:08:02,900 bod je stejný. 184 00:08:02,900 --> 00:08:05,030 Kdybychom hledali pro 17, mělo by to 185 00:08:05,030 --> 00:08:08,870 byl v poli, a počáteční bod a koncový bod té poslední iterace 186 00:08:08,870 --> 00:08:11,820 Než ty body přešel, bychom našli 17 tam. 187 00:08:11,820 --> 00:08:15,510 Je to pouze tehdy, když překročí, že můžeme zaručit, že element není 188 00:08:15,510 --> 00:08:17,180 existují v matici. 189 00:08:17,180 --> 00:08:20,260 >> Takže pojďme se hodně méně Kroky než lineární hledání. 190 00:08:20,260 --> 00:08:23,250 V nejhorším případě, měli jsme rozdělit se stanoví seznam n elementy 191 00:08:23,250 --> 00:08:27,770 opakovaně na polovinu najít cíl, a to buď proto, že cílový prvek 192 00:08:27,770 --> 00:08:33,110 bude někde v poslední divize, nebo neexistuje vůbec. 193 00:08:33,110 --> 00:08:37,830 Takže v nejhorším případě, musíme rozešli se array-- to víte? 194 00:08:37,830 --> 00:08:40,510 Log n časy; my muset snížit problém 195 00:08:40,510 --> 00:08:42,610 v polovině určitého počtu dob. 196 00:08:42,610 --> 00:08:45,160 To, kolikrát je log n. 197 00:08:45,160 --> 00:08:46,510 >> Jaký je nejlepší scénář? 198 00:08:46,510 --> 00:08:48,899 No, poprvé, kdy jsme vypočítat střed, 199 00:08:48,899 --> 00:08:50,190 najdeme to, co hledáme. 200 00:08:50,190 --> 00:08:52,150 Ve všech předchozí příklady na binární vyhledávání 201 00:08:52,150 --> 00:08:55,489 jsme právě probírali, kdybychom měli Hledal prvku 15, 202 00:08:55,489 --> 00:08:57,030 bychom zjistili, že okamžitě. 203 00:08:57,030 --> 00:08:58,321 To bylo na samém počátku. 204 00:08:58,321 --> 00:09:01,200 To byl střed První pokus o rozdělení 205 00:09:01,200 --> 00:09:03,950 z divize v binárním vyhledávání. 206 00:09:03,950 --> 00:09:06,350 >> A tak v nejhorším Případ, binární vyhledávání běží 207 00:09:06,350 --> 00:09:11,580 v log n, což je podstatně lepší než lineární vyhledávání, v nejhorším případě. 208 00:09:11,580 --> 00:09:16,210 V nejlepším případě, binární Vyhledávání probíhá v omega 1. 209 00:09:16,210 --> 00:09:18,990 Takže binární vyhledávání je hodně lepší než lineární vyhledávání, 210 00:09:18,990 --> 00:09:23,270 ale budete muset vypořádat s procesem třídění své pole dřív, než si můžete 211 00:09:23,270 --> 00:09:26,140 využít sílu binárního vyhledávání. 212 00:09:26,140 --> 00:09:27,130 >> Jsem Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 To je CS 50. 214 00:09:29,470 --> 00:09:31,070