1 00:00:00,000 --> 00:00:03,346 >> [Bermain muzik] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> DOUG LLOYD: Baiklah. 4 00:00:06,220 --> 00:00:08,140 Jadi carian binari adalah algoritma kita boleh menggunakan 5 00:00:08,140 --> 00:00:10,530 untuk mencari satu elemen dalam array. 6 00:00:10,530 --> 00:00:14,710 Tidak seperti carian linear, ia memerlukan syarat khas dipenuhi terlebih dahulu, 7 00:00:14,710 --> 00:00:19,020 tetapi ia begitu jauh lebih efisien jika bahawa keadaan adalah, sebenarnya, dipenuhi. 8 00:00:19,020 --> 00:00:20,470 >> Jadi apa idea di sini? 9 00:00:20,470 --> 00:00:21,780 ia pecah dan perintah. 10 00:00:21,780 --> 00:00:25,100 Kami mahu mengurangkan saiz kawasan carian dengan separuh setiap kali 11 00:00:25,100 --> 00:00:27,240 untuk mencari beberapa sasaran. 12 00:00:27,240 --> 00:00:29,520 Ini adalah di mana syarat datang ke dalam bermain, walaupun. 13 00:00:29,520 --> 00:00:32,740 Kita hanya boleh memanfaatkan kuasa menghapuskan separuh daripada unsur-unsur 14 00:00:32,740 --> 00:00:36,070 tanpa melihat mereka jika array disusun. 15 00:00:36,070 --> 00:00:39,200 >> Jika ia merupakan satu campuran lengkap up, kita tidak boleh hanya keluar dari tangan 16 00:00:39,200 --> 00:00:42,870 membuang separuh daripada unsur-unsur, kerana kita tidak tahu apa yang kita membuang. 17 00:00:42,870 --> 00:00:45,624 Tetapi jika lokasi itu disusun, kita boleh berbuat demikian, kerana kita 18 00:00:45,624 --> 00:00:48,040 tahu bahawa segala-galanya kepada kiri di mana kita masa ini 19 00:00:48,040 --> 00:00:50,500 mesti lebih rendah daripada nilai kita pada masa ini. 20 00:00:50,500 --> 00:00:52,300 Dan segala-galanya kepada kanan di mana kita berada 21 00:00:52,300 --> 00:00:55,040 mesti lebih besar daripada nilai kami sedang melihat. 22 00:00:55,040 --> 00:00:58,710 >> Jadi apa pseudokod langkah-langkah untuk carian binari? 23 00:00:58,710 --> 00:01:02,310 Kami mengulangi proses ini sehingga pelbagai atau, seperti yang kita meneruskan melalui, 24 00:01:02,310 --> 00:01:07,740 array sub, bahagian yang lebih kecil daripada pelbagai asal, adalah saiz 0. 25 00:01:07,740 --> 00:01:10,960 Kira titik tengah sub lokasi semasa. 26 00:01:10,960 --> 00:01:14,460 >> Jika nilai yang anda cari adalah dalam elemen array, berhenti. 27 00:01:14,460 --> 00:01:15,030 Anda menjumpainya. 28 00:01:15,030 --> 00:01:16,550 Itu yang besar. 29 00:01:16,550 --> 00:01:19,610 Jika tidak, jika sasaran adalah kurang daripada apa yang di tengah-tengah, 30 00:01:19,610 --> 00:01:23,430 jadi jika nilai kita sedang adalah lebih rendah daripada apa yang kita lihat, 31 00:01:23,430 --> 00:01:26,780 mengulangi proses ini sekali lagi, tetapi menukar titik akhir, dan bukannya 32 00:01:26,780 --> 00:01:29,300 menjadi asal melengkapkan pelbagai penuh, 33 00:01:29,300 --> 00:01:34,110 menjadi hanya ke kiri di mana kita hanya melihat. 34 00:01:34,110 --> 00:01:38,940 >> Kami tahu bahawa tengah-tengah adalah terlalu tinggi, atau sasaran itu kurang daripada tengah-tengah, 35 00:01:38,940 --> 00:01:42,210 dan oleh itu mesti wujud, jika ia wujud sama sekali dalam array, 36 00:01:42,210 --> 00:01:44,660 di suatu tempat di sebelah kiri titik tengah. 37 00:01:44,660 --> 00:01:48,120 Dan dengan itu kita akan menetapkan array lokasi hanya ke kiri 38 00:01:48,120 --> 00:01:51,145 daripada titik tengah sebagai titik akhir baru. 39 00:01:51,145 --> 00:01:53,770 Sebaliknya, jika sasaran adalah lebih besar daripada apa yang di tengah-tengah, 40 00:01:53,770 --> 00:01:55,750 kami melakukan yang sama proses, tetapi sebaliknya kita 41 00:01:55,750 --> 00:01:59,520 menukar titik permulaan untuk menjadi hanya di sebelah kanan titik tengah 42 00:01:59,520 --> 00:02:00,680 kita hanya dikira. 43 00:02:00,680 --> 00:02:03,220 Dan kemudian, kita memulakan proses lagi. 44 00:02:03,220 --> 00:02:05,220 >> Mari kita menggambarkan hal ini, OK? 45 00:02:05,220 --> 00:02:08,620 Jadi ada banyak berlaku dan di sini, tetapi di sini adalah pelbagai daripada 15 elemen. 46 00:02:08,620 --> 00:02:11,400 Dan kita akan dapat mengesan daripada banyak lagi barangan masa ini. 47 00:02:11,400 --> 00:02:13,870 Jadi, dalam carian linear, kami hanya mengambil berat tentang sasaran. 48 00:02:13,870 --> 00:02:15,869 Tetapi kali ini kita mahu mengambil berat tentang di mana kita 49 00:02:15,869 --> 00:02:18,480 mula kelihatan, di mana kita berhenti mencari, 50 00:02:18,480 --> 00:02:21,876 dan apa yang titik tengah array semasa. 51 00:02:21,876 --> 00:02:23,250 Jadi di sini kita pergi dengan carian binari. 52 00:02:23,250 --> 00:02:25,290 Kami cukup banyak yang baik untuk pergi, bukan? 53 00:02:25,290 --> 00:02:28,650 Saya hanya akan meletakkan bawah sini satu set indeks. 54 00:02:28,650 --> 00:02:32,430 Ini adalah pada dasarnya apa unsur array kita berbicara tentang. 55 00:02:32,430 --> 00:02:34,500 Dengan carian linear, kita peduli, bukankah kita 56 00:02:34,500 --> 00:02:36,800 perlu tahu berapa banyak unsur-unsur yang kita iterating ke atas, 57 00:02:36,800 --> 00:02:40,010 tetapi kita tidak benar-benar peduli apa elemen kami sedang melihat. 58 00:02:40,010 --> 00:02:41,014 Dalam mencari binari, kita lakukan. 59 00:02:41,014 --> 00:02:42,930 Dan supaya orang-orang yang hanya ada sebagai panduan sedikit. 60 00:02:42,930 --> 00:02:44,910 >> Oleh itu, kita boleh mula, bukan? 61 00:02:44,910 --> 00:02:46,240 Well, tidak cukup. 62 00:02:46,240 --> 00:02:48,160 Ingat apa yang saya katakan tentang carian binari? 63 00:02:48,160 --> 00:02:50,955 Kita tidak boleh melakukannya pada lokasi terisih atau yang lain, 64 00:02:50,955 --> 00:02:55,820 kami tidak memberi jaminan bahawa unsur-unsur atau nilai-nilai tertentu tidak 65 00:02:55,820 --> 00:02:57,650 tidak sengaja dibuang apabila kita hanya 66 00:02:57,650 --> 00:02:59,920 memutuskan untuk mengabaikan separuh daripada array. 67 00:02:59,920 --> 00:03:02,574 >> Jadi langkah satu dengan carian binari adalah anda mesti mempunyai lokasi disusun. 68 00:03:02,574 --> 00:03:05,240 Dan anda boleh menggunakan mana-mana pengasingan algoritma kita telah bercakap tentang 69 00:03:05,240 --> 00:03:06,700 untuk mendapatkan anda untuk kedudukan itu. 70 00:03:06,700 --> 00:03:10,370 Oleh sebab itu, kita berada dalam kedudukan di mana kita boleh melakukan carian binari. 71 00:03:10,370 --> 00:03:12,560 >> Jadi mari kita mengulangi proses tersebut langkah demi langkah dan 72 00:03:12,560 --> 00:03:14,830 mengesan apa yang berlaku seperti yang kita pergi. 73 00:03:14,830 --> 00:03:17,980 Oleh itu, pertama yang perlu kita lakukan ialah mengira titik tengah lokasi semasa. 74 00:03:17,980 --> 00:03:20,620 Baiklah, kami akan mengatakan bahawa kita berada, pertama semua, mencari nilai 19. 75 00:03:20,620 --> 00:03:22,290 Kami cuba untuk mencari bilangan 19. 76 00:03:22,290 --> 00:03:25,380 Elemen pertama ini lokasi terletak di indeks sifar, 77 00:03:25,380 --> 00:03:28,880 dan elemen terakhir ini lokasi terletak di indeks 14. 78 00:03:28,880 --> 00:03:31,430 Dan dengan itu kita akan memanggil mereka yang mula dan akhir. 79 00:03:31,430 --> 00:03:35,387 >> Oleh itu, kita mengira titik tengah oleh menambah 0 tambah 14 dibahagikan dengan 2; 80 00:03:35,387 --> 00:03:36,720 titik tengah agak mudah. 81 00:03:36,720 --> 00:03:40,190 Dan kita boleh mengatakan bahawa titik tengah itu kini 7. 82 00:03:40,190 --> 00:03:43,370 Begitu juga 15 apa yang kami cari? 83 00:03:43,370 --> 00:03:43,940 Tidak. 84 00:03:43,940 --> 00:03:45,270 Kami sedang mencari 19. 85 00:03:45,270 --> 00:03:49,400 Tetapi kita tahu bahawa 19 adalah lebih besar daripada apa yang kita dapati di tengah-tengah. 86 00:03:49,400 --> 00:03:52,470 >> Jadi apa yang kita boleh lakukan ialah menukar titik permulaan 87 00:03:52,470 --> 00:03:57,280 menjadi hanya di sebelah kanan yang titik tengah, dan mengulangi proses tersebut lagi. 88 00:03:57,280 --> 00:04:01,690 Dan apabila kita berbuat demikian, kita sekarang mengatakan titik permulaan yang baru adalah lokasi mudah 8. 89 00:04:01,690 --> 00:04:07,220 Apa yang kita telah dilakukan dengan berkesan adalah semua yang diabaikan di sebelah kiri 15. 90 00:04:07,220 --> 00:04:09,570 Kami telah dihapuskan separuh masalah ini, dan kini, 91 00:04:09,570 --> 00:04:13,510 daripada harus mencari lebih 15 elemen dalam array kita, 92 00:04:13,510 --> 00:04:15,610 kita hanya perlu mencari lebih 7. 93 00:04:15,610 --> 00:04:17,706 Jadi 8 adalah titik permulaan yang baru. 94 00:04:17,706 --> 00:04:19,600 14 masih titik akhir. 95 00:04:19,600 --> 00:04:21,430 >> Dan sekarang, kami akan ke ini lagi. 96 00:04:21,430 --> 00:04:22,810 Kami mengira titik tengah baru. 97 00:04:22,810 --> 00:04:27,130 8 campur 14 adalah 22, dibahagikan dengan 2 adalah 11. 98 00:04:27,130 --> 00:04:28,660 Adakah ini yang kita cari? 99 00:04:28,660 --> 00:04:30,110 Tidak. 100 00:04:30,110 --> 00:04:32,930 Kami sedang mencari satu nilai yang kurang daripada apa yang kita hanya dijumpai. 101 00:04:32,930 --> 00:04:34,721 Jadi, kita akan mengulangi proses sekali lagi. 102 00:04:34,721 --> 00:04:38,280 Kami akan menukar titik akhir untuk hanya di sebelah kiri titik tengah. 103 00:04:38,280 --> 00:04:41,800 Jadi titik akhir baru menjadi 10. 104 00:04:41,800 --> 00:04:44,780 Dan sekarang, itu hanya sebahagian daripada array kita perlu menyusun melalui. 105 00:04:44,780 --> 00:04:48,460 Oleh itu, kita kini telah dihapuskan 12 daripada 15 elemen. 106 00:04:48,460 --> 00:04:51,550 Kita tahu bahawa jika 19 wujud dalam array, ia 107 00:04:51,550 --> 00:04:57,210 mesti wujud di suatu tempat antara elemen nombor 8 dan unsur nombor 10. 108 00:04:57,210 --> 00:04:59,400 >> Oleh itu, kita mengira titik tengah baru lagi. 109 00:04:59,400 --> 00:05:02,900 8 campur 10 adalah 18, dibahagikan dengan 2 adalah 9. 110 00:05:02,900 --> 00:05:05,074 Dan dalam kes ini, melihat, yang sasaran adalah di tengah-tengah. 111 00:05:05,074 --> 00:05:06,740 Kami mendapati apa yang kita cari. 112 00:05:06,740 --> 00:05:07,780 Kita boleh berhenti. 113 00:05:07,780 --> 00:05:10,561 Kami berjaya menamatkan carian binari. 114 00:05:10,561 --> 00:05:11,060 Baiklah. 115 00:05:11,060 --> 00:05:13,930 Jadi kita tahu algoritma ini berfungsi jika sasaran adalah 116 00:05:13,930 --> 00:05:16,070 suatu tempat di dalam array. 117 00:05:16,070 --> 00:05:19,060 Adakah ini kerja algoritma jika sasaran itu tidak berada dalam array? 118 00:05:19,060 --> 00:05:20,810 Nah, mari kita memulakannya sekali lagi, dan kali ini, 119 00:05:20,810 --> 00:05:23,380 mari kita lihat untuk elemen 16, yang secara visual kita dapat melihat 120 00:05:23,380 --> 00:05:25,620 tidak wujud mana-mana sahaja dalam array. 121 00:05:25,620 --> 00:05:27,110 >> Titik permulaan sekali lagi 0. 122 00:05:27,110 --> 00:05:28,590 Titik akhir sekali lagi 14. 123 00:05:28,590 --> 00:05:32,490 Mereka adalah indeks yang pertama dan elemen terakhir array lengkap. 124 00:05:32,490 --> 00:05:36,057 Dan kita akan melalui proses yang kita hanya lalui lagi, cuba untuk mencari 16, 125 00:05:36,057 --> 00:05:39,140 walaupun cacat, kita boleh sudah memberitahu bahawa ia tidak akan berada di sana. 126 00:05:39,140 --> 00:05:43,450 Kami hanya mahu memastikan algoritma ini akan, sebenarnya, masih bekerja dalam beberapa cara 127 00:05:43,450 --> 00:05:46,310 dan bukan hanya meninggalkan kita terperangkap dalam gelung tak terhingga. 128 00:05:46,310 --> 00:05:48,190 >> Jadi apa langkah pertama? 129 00:05:48,190 --> 00:05:50,230 Kira titik tengah array semasa. 130 00:05:50,230 --> 00:05:52,790 Apakah titik tengah array semasa? 131 00:05:52,790 --> 00:05:54,410 Nah, ia adalah 7, bukan? 132 00:05:54,410 --> 00:05:57,560 14 tambah 0 dibahagikan dengan 2 adalah 7. 133 00:05:57,560 --> 00:05:59,280 15 apa yang kami cari? 134 00:05:59,280 --> 00:05:59,780 No. 135 00:05:59,780 --> 00:06:02,930 Ia agak rapat, tetapi kami tidak sabar- untuk nilai yang lebih besar sedikit daripada itu. 136 00:06:02,930 --> 00:06:06,310 >> Jadi kita tahu bahawa ia akan menjadi tempat untuk sebelah kiri 15. 137 00:06:06,310 --> 00:06:08,540 Sasaran adalah lebih besar daripada apa yang di titik tengah. 138 00:06:08,540 --> 00:06:12,450 Dan dengan itu kita menetapkan titik permulaan yang baru untuk hanya di sebelah kanan tengah-tengah. 139 00:06:12,450 --> 00:06:16,130 Titik tengah itu kini 7, jadi katakan titik permulaan baru adalah 8. 140 00:06:16,130 --> 00:06:18,130 Dan apa yang kita ada dengan berkesan dilakukan sekali lagi diabaikan 141 00:06:18,130 --> 00:06:21,150 separuh kiri keseluruhan array. 142 00:06:21,150 --> 00:06:23,750 >> Sekarang, kita mengulangi memproses sekali lagi. 143 00:06:23,750 --> 00:06:24,910 Kira titik tengah baru. 144 00:06:24,910 --> 00:06:29,350 8 campur 14 adalah 22, dibahagikan dengan 2 adalah 11. 145 00:06:29,350 --> 00:06:31,060 Adalah 23 apa yang kami cari? 146 00:06:31,060 --> 00:06:31,870 Malangnya tidak. 147 00:06:31,870 --> 00:06:34,930 Kami sedang mencari nilai yang yang kurang daripada 23. 148 00:06:34,930 --> 00:06:37,850 Dan sebagainya dalam kes ini, kita akan untuk menukar titik akhir menjadi hanya 149 00:06:37,850 --> 00:06:40,035 di sebelah kiri titik tengah semasa. 150 00:06:40,035 --> 00:06:43,440 Titik tengah semasa adalah 11, dan jadi kita akan menetapkan titik akhir baru 151 00:06:43,440 --> 00:06:46,980 untuk masa yang akan datang kita pergi melalui proses ini hingga 10. 152 00:06:46,980 --> 00:06:48,660 >> Sekali lagi, kita melalui proses lagi. 153 00:06:48,660 --> 00:06:49,640 Kira titik tengah. 154 00:06:49,640 --> 00:06:53,100 8 ditambah 10 dibahagikan dengan 2 adalah 9. 155 00:06:53,100 --> 00:06:54,750 Adalah 19 apa yang kami cari? 156 00:06:54,750 --> 00:06:55,500 Malangnya tidak. 157 00:06:55,500 --> 00:06:58,050 Kami masih mencari bilangan yang kurang daripada itu. 158 00:06:58,050 --> 00:07:02,060 Oleh itu, kita akan menukar titik akhir masa ini menjadi hanya di sebelah kiri titik tengah. 159 00:07:02,060 --> 00:07:05,532 Titik tengah itu kini 9, jadi titik akhir akan 8. 160 00:07:05,532 --> 00:07:07,920 Dan kini, kami hanya mencari di pelbagai elemen. 161 00:07:07,920 --> 00:07:10,250 >> Apakah titik tengah pelbagai ini? 162 00:07:10,250 --> 00:07:13,459 Nah, ia bermula pada 8, ia berakhir pada 8, titik tengah adalah 8. 163 00:07:13,459 --> 00:07:14,750 Adakah itu yang kita cari? 164 00:07:14,750 --> 00:07:16,339 Adakah kita mencari 17? 165 00:07:16,339 --> 00:07:17,380 Tidak, kami mencari 16. 166 00:07:17,380 --> 00:07:20,160 Jadi, jika ia wujud dalam array, ia mesti wujud di suatu tempat 167 00:07:20,160 --> 00:07:21,935 sebelah kiri di mana kita kini berada. 168 00:07:21,935 --> 00:07:23,060 Jadi apa yang kita akan lakukan? 169 00:07:23,060 --> 00:07:26,610 Baiklah, kami akan menetapkan titik akhirnya menjadi hanya di sebelah kiri titik tengah semasa. 170 00:07:26,610 --> 00:07:29,055 Oleh itu, kita akan menukar titik akhir hingga 7. 171 00:07:29,055 --> 00:07:32,120 Adakah anda melihat apa yang hanya yang berlaku di sini, walaupun? 172 00:07:32,120 --> 00:07:33,370 Lihatlah di sini sekarang. 173 00:07:33,370 --> 00:07:35,970 >> Mula kini lebih besar daripada akhir. 174 00:07:35,970 --> 00:07:39,620 Berkesan, kedua-dua hujung pelbagai kami telah berpindah, 175 00:07:39,620 --> 00:07:42,252 dan titik permulaan adalah kini selepas titik akhir. 176 00:07:42,252 --> 00:07:43,960 Nah, yang tidak masuk akal, bukan? 177 00:07:43,960 --> 00:07:47,960 Oleh sebab itu, apa yang kita boleh katakan ialah kita mempunyai pelbagai sub saiz 0. 178 00:07:47,960 --> 00:07:50,110 Dan apabila kita mendapat ke ketika ini, kita kini boleh 179 00:07:50,110 --> 00:07:53,940 menjamin elemen yang 16 tidak wujud dalam array, 180 00:07:53,940 --> 00:07:56,280 kerana titik permulaan dan titik akhir telah melintasi. 181 00:07:56,280 --> 00:07:58,340 Dan oleh itu tidak ada. 182 00:07:58,340 --> 00:08:01,340 Sekarang, perhatikan bahawa ini adalah sedikit berbeza daripada titik mula dan akhir 183 00:08:01,340 --> 00:08:02,900 menunjukkan adalah sama. 184 00:08:02,900 --> 00:08:05,030 Jika kita telah mencari 17, ia akan mempunyai 185 00:08:05,030 --> 00:08:08,870 berada dalam array, dan titik permulaan dan titik akhir yang lelaran lalu 186 00:08:08,870 --> 00:08:11,820 sebelum mata tersebut melintasi, kita akan mendapati 17 di sana. 187 00:08:11,820 --> 00:08:15,510 Ia hanya apabila mereka melintas yang kita boleh menjamin bahawa unsur tidak 188 00:08:15,510 --> 00:08:17,180 wujud dalam array. 189 00:08:17,180 --> 00:08:20,260 >> Jadi mari kita mengambil masa yang lebih sedikit langkah-langkah daripada carian linear. 190 00:08:20,260 --> 00:08:23,250 Dalam kes yang teruk, kami terpaksa berpecah senarai n unsur 191 00:08:23,250 --> 00:08:27,770 berulang kali pada separuh untuk mencari sasaran, sama ada kerana elemen sasaran 192 00:08:27,770 --> 00:08:33,110 akan menjadi suatu tempat di lepas bahagian, atau ia tidak wujud sama sekali. 193 00:08:33,110 --> 00:08:37,830 Jadi dalam kes yang paling teruk, kita perlu berpecah array-- yang anda tahu? 194 00:08:37,830 --> 00:08:40,510 Log n masa; kita perlu memotong masalah 195 00:08:40,510 --> 00:08:42,610 dalam setengah beberapa kali. 196 00:08:42,610 --> 00:08:45,160 Yang beberapa kali adalah log n. 197 00:08:45,160 --> 00:08:46,510 >> Apakah senario kes terbaik? 198 00:08:46,510 --> 00:08:48,899 Well, masa kita mula-mula mengira titik tengah, 199 00:08:48,899 --> 00:08:50,190 kita mencari apa yang kita cari. 200 00:08:50,190 --> 00:08:52,150 Dalam semua sebelumnya contoh pada carian binari 201 00:08:52,150 --> 00:08:55,489 kita baru sahaja pergi ke atas, jika kita mempunyai cari selama unsur 15, 202 00:08:55,489 --> 00:08:57,030 kita akan mendapati bahawa dengan segera. 203 00:08:57,030 --> 00:08:58,321 Itu adalah pada awal-awal. 204 00:08:58,321 --> 00:09:01,200 Itu adalah titik tengah percubaan pertama di perpecahan 205 00:09:01,200 --> 00:09:03,950 satu bahagian dalam carian binari. 206 00:09:03,950 --> 00:09:06,350 >> Jadi dengan yang paling teruk kes, carian binari berjalan 207 00:09:06,350 --> 00:09:11,580 dalam log n, harga yang jauh lebih baik daripada carian linear, dalam kes yang paling teruk. 208 00:09:11,580 --> 00:09:16,210 Dalam kes ini, binari carian berjalan dalam omega 1. 209 00:09:16,210 --> 00:09:18,990 Jadi carian binari adalah banyak lebih baik daripada carian linear, 210 00:09:18,990 --> 00:09:23,270 tetapi anda perlu berurusan dengan proses menyusun pelbagai anda terlebih dahulu sebelum anda boleh 211 00:09:23,270 --> 00:09:26,140 memanfaatkan kuasa carian binari. 212 00:09:26,140 --> 00:09:27,130 >> Saya Doug Lloyd. 213 00:09:27,130 --> 00:09:29,470 Ini adalah CS 50. 214 00:09:29,470 --> 00:09:31,070