1 00:00:00,000 --> 00:00:03,346 >> [MÜZİK OYUN] 2 00:00:03,346 --> 00:00:05,258 3 00:00:05,258 --> 00:00:06,220 >> Doug LLOYD: Pekala. 4 00:00:06,220 --> 00:00:08,140 Yani ikili arama bir olduğunu Kullanabileceğimiz algoritma 5 00:00:08,140 --> 00:00:10,530 Bir dizinin içinde bir unsuru bulmak için. 6 00:00:10,530 --> 00:00:14,710 Doğrusal arama aksine, gerektiren bir özel durum, önceden yerine getirilmesi 7 00:00:14,710 --> 00:00:19,020 ama çok daha verimli, eğer var durum olduğunu, aslında, bir araya geldi. 8 00:00:19,020 --> 00:00:20,470 >> Yani fikir burada ne var? 9 00:00:20,470 --> 00:00:21,780 o böl ve fethet var. 10 00:00:21,780 --> 00:00:25,100 Biz boyutunu küçültmek istiyorum Yarım her zaman arama alanı 11 00:00:25,100 --> 00:00:27,240 Bir hedef numarasını bulmak için. 12 00:00:27,240 --> 00:00:29,520 Bu nerede durumdur olsa da, devreye giriyor. 13 00:00:29,520 --> 00:00:32,740 Biz sadece gücünü kullanabiliyorlar elementlerin ortadan yarısı 14 00:00:32,740 --> 00:00:36,070 Hatta bakmadan Onları dizi sıralanır eğer. 15 00:00:36,070 --> 00:00:39,200 >> Tam bir karışım kadar ise, biz sadece yandan dışarı olamaz 16 00:00:39,200 --> 00:00:42,870 Çünkü, elemanların yarısı atmak biz atarak biliyorum bilmiyorum. 17 00:00:42,870 --> 00:00:45,624 Ama dizi sıralanır eğer biz yapabilir çünkü biz 18 00:00:45,624 --> 00:00:48,040 o her şeyi biliyor Şu anda nerede sol 19 00:00:48,040 --> 00:00:50,500 daha düşük olmalıdır değer şu anda konum. 20 00:00:50,500 --> 00:00:52,300 Ve her şey için Nerede doğru 21 00:00:52,300 --> 00:00:55,040 değerinden daha büyük olmalıdır Şu anda bakıyoruz. 22 00:00:55,040 --> 00:00:58,710 >> Peki pseudocode ne İkili arama için adımlar? 23 00:00:58,710 --> 00:01:02,310 Biz gelene kadar bu işlemi tekrarlayın dizi ya, biz aracılığıyla ilerlerken, 24 00:01:02,310 --> 00:01:07,740 alt diziler, küçük parçalar Orijinal dizinin boyutu 0 olduğunu. 25 00:01:07,740 --> 00:01:10,960 Orta noktayı hesaplayın Geçerli alt dizinin. 26 00:01:10,960 --> 00:01:14,460 >> Aradığınız bir değerse Dizinin bu elemanın, dur. 27 00:01:14,460 --> 00:01:15,030 Buldun. 28 00:01:15,030 --> 00:01:16,550 Bu harika. 29 00:01:16,550 --> 00:01:19,610 Aksi takdirde, hedef ise, ortasında ne daha az, 30 00:01:19,610 --> 00:01:23,430 bu yüzden değeri eğer arıyoruz için biz ne görmek daha düşüktür 31 00:01:23,430 --> 00:01:26,780 Yine bu işlemi tekrarlayın, ancak Bunun yerine, bitiş noktasını değiştirmek 32 00:01:26,780 --> 00:01:29,300 Orijinal olma tam bir dizi tamamlamak, 33 00:01:29,300 --> 00:01:34,110 Sadece sola olmak nerede biz sadece baktı. 34 00:01:34,110 --> 00:01:38,940 >> Biz, orta çok yüksek olduğunu biliyordu veya hedef ortadan daha az 35 00:01:38,940 --> 00:01:42,210 ve bu nedenle, bulunmalıdır bunun ise , tüm dizide var 36 00:01:42,210 --> 00:01:44,660 yerde orta sol. 37 00:01:44,660 --> 00:01:48,120 Ve böylece biz dizi set edeceğiz Sadece sola yeri 38 00:01:48,120 --> 00:01:51,145 yeni son noktası olarak orta evi. 39 00:01:51,145 --> 00:01:53,770 Bunun aksine, hedef ise, ortasında ne büyüktür, 40 00:01:53,770 --> 00:01:55,750 biz tam aynı şeyi süreç, ancak bunun yerine biz 41 00:01:55,750 --> 00:01:59,520 olmak üzere başlangıç ​​noktasını değiştirmek Sadece orta sağında 42 00:01:59,520 --> 00:02:00,680 biz sadece hesapladı. 43 00:02:00,680 --> 00:02:03,220 Ve sonra, biz tekrar işlemine başlamak. 44 00:02:03,220 --> 00:02:05,220 >> En Tamam, bu görselleştirmek edelim? 45 00:02:05,220 --> 00:02:08,620 Yani gidiş ve burada bir çok şey var, ama burada 15 elemanlı bir dizi var. 46 00:02:08,620 --> 00:02:11,400 Ve biz takip için gidiyoruz çok daha fazla şeyler bu sefer. 47 00:02:11,400 --> 00:02:13,870 Yani doğrusal arama, biz Sadece bir hedefe hakkında bakmakta. 48 00:02:13,870 --> 00:02:15,869 Ama bu sefer biz istiyoruz biz nerede umurumda 49 00:02:15,869 --> 00:02:18,480 bakmak için başlangıç, nerede biz arıyoruz duruyoruz, 50 00:02:18,480 --> 00:02:21,876 ve orta ne Geçerli dizinin. 51 00:02:21,876 --> 00:02:23,250 Yani burada biz ikili arama ile gitmek. 52 00:02:23,250 --> 00:02:25,290 Biz hoş çok iyi gitmek, haklısın? 53 00:02:25,290 --> 00:02:28,650 Ben sadece aşağı koymak için gidiyorum endeksleri bir dizi aşağıda. 54 00:02:28,650 --> 00:02:32,430 Bu temelde sadece ne unsurdur Dizinin bahsediyoruz. 55 00:02:32,430 --> 00:02:34,500 Doğrusal arama, biz biz mademki, bakım 56 00:02:34,500 --> 00:02:36,800 Kaç bilmeniz gerekir Biz yineleme konum elemanları, 57 00:02:36,800 --> 00:02:40,010 ama biz aslında umurumda değil eleman şu anda bakıyoruz. 58 00:02:40,010 --> 00:02:41,014 İkili arama, biz bunu. 59 00:02:41,014 --> 00:02:42,930 Ve böylece bu sadece vardır Orada biraz rehber olarak. 60 00:02:42,930 --> 00:02:44,910 >> Bu yüzden, doğru başlayabiliriz? 61 00:02:44,910 --> 00:02:46,240 Peki, tam olarak değil. 62 00:02:46,240 --> 00:02:48,160 Ne dediğimi hatırlamıyorum İkili arama hakkında? 63 00:02:48,160 --> 00:02:50,955 Biz bunu yapamaz Başka ayrımı yapılmamış diğer dizi veya 64 00:02:50,955 --> 00:02:55,820 biz garanti değil Belirli öğeleri veya değerler değil 65 00:02:55,820 --> 00:02:57,650 Yanlışlıkla olmak atılan zaman biz sadece 66 00:02:57,650 --> 00:02:59,920 Dizinin yarısını görmezden karar verirler. 67 00:02:59,920 --> 00:03:02,574 >> Yani ikili arama ile bir adım Eğer sıralanmış dizi olması gerekir. 68 00:03:02,574 --> 00:03:05,240 Ve sıralama birini kullanabilirsiniz biz konuştuk algoritmalar 69 00:03:05,240 --> 00:03:06,700 Bu pozisyona almak için. 70 00:03:06,700 --> 00:03:10,370 Yani şimdi biz bir pozisyonda nerede konum Biz ikili arama yapabilirsiniz. 71 00:03:10,370 --> 00:03:12,560 >> Öyleyse işlemi yineleyin edelim adım adım ve tutmak 72 00:03:12,560 --> 00:03:14,830 Biz giderken neler olup bittiğini izlemek. 73 00:03:14,830 --> 00:03:17,980 Bu yüzden ilk biz hesaplamak yapmanız gereken Geçerli dizinin orta. 74 00:03:17,980 --> 00:03:20,620 Peki, biz ilk biz sen söyleyeceğim tüm değeri 19 arıyorum. 75 00:03:20,620 --> 00:03:22,290 Biz sayı 19 bulmaya çalışıyoruz. 76 00:03:22,290 --> 00:03:25,380 Bu ilk elemanı Dizi, endeks sıfır yer almaktadır 77 00:03:25,380 --> 00:03:28,880 ve bu son elemanı Dizi indeksi 14 yer almaktadır. 78 00:03:28,880 --> 00:03:31,430 Ve bu yüzden bu başlangıç ​​ve bitiş arayacağım. 79 00:03:31,430 --> 00:03:35,387 >> Bu yüzden orta noktayı göre hesaplamak 0 artı 2 bölü 14 eklenmesi; 80 00:03:35,387 --> 00:03:36,720 oldukça basit orta. 81 00:03:36,720 --> 00:03:40,190 Ve biz söyleyebiliriz orta noktası artık 7'dir. 82 00:03:40,190 --> 00:03:43,370 Yani 15 Aradığımız nedir? 83 00:03:43,370 --> 00:03:43,940 Hayır değil. 84 00:03:43,940 --> 00:03:45,270 Biz 19 arıyoruz. 85 00:03:45,270 --> 00:03:49,400 Ama biz 19 daha fazla olduğunu biliyoruz Biz ortada bulunan olandan. 86 00:03:49,400 --> 00:03:52,470 >> Yani biz ne yapabilirim Başlangıç ​​noktasını değiştirmek 87 00:03:52,470 --> 00:03:57,280 Sadece sağ olmak orta ve süreci tekrarlayın. 88 00:03:57,280 --> 00:04:01,690 Biz bunu yaparken, biz şimdi söylemek Yeni bir başlangıç ​​noktası dizisi yeri 8'dir. 89 00:04:01,690 --> 00:04:07,220 Ne biz etkili yaptık olduğunu 15 sol göz ardı her şeyi. 90 00:04:07,220 --> 00:04:09,570 Biz yarısını ortadan kaldırmış olduk Sorunun, ve şimdi, 91 00:04:09,570 --> 00:04:13,510 Bunun yerine aramak zorunda Bizim dizide üzerinde 15 elemanları, 92 00:04:13,510 --> 00:04:15,610 biz sadece 7 üzerinde aramak zorunda. 93 00:04:15,610 --> 00:04:17,706 Yani 8 yeni bir başlangıç ​​noktasıdır. 94 00:04:17,706 --> 00:04:19,600 14 hala son noktasıdır. 95 00:04:19,600 --> 00:04:21,430 >> Ve şimdi, biz yine bu üzerine gitmek. 96 00:04:21,430 --> 00:04:22,810 Yeni orta noktayı hesaplar. 97 00:04:22,810 --> 00:04:27,130 8 artı 14 2 11 olduğu bölü 22 olduğunu. 98 00:04:27,130 --> 00:04:28,660 Bu bizim aradığımız şey mi? 99 00:04:28,660 --> 00:04:30,110 Hayır değil. 100 00:04:30,110 --> 00:04:32,930 Biz bu değeri arıyorsanız biz sadece ne bulduğumuz daha az. 101 00:04:32,930 --> 00:04:34,721 Bu yüzden tekrar gidiyoruz Tekrar süreci. 102 00:04:34,721 --> 00:04:38,280 Biz son noktayı değiştirmek için gidiyoruz Sadece orta solunda olacak. 103 00:04:38,280 --> 00:04:41,800 Yani yeni uç nokta 10 olur. 104 00:04:41,800 --> 00:04:44,780 Ve şimdi, bu sadece bir parçası Dizi biz aracılığıyla sıralamak zorunda. 105 00:04:44,780 --> 00:04:48,460 Yani biz şimdi ortadan kaldırdık 15 elemanları 12. 106 00:04:48,460 --> 00:04:51,550 Biz biliyoruz 19 eğer dizide olup, bu 107 00:04:51,550 --> 00:04:57,210 elemanı arasında bir yerde bulunmalıdır 8 sayısı ve eleman sayısı 10. 108 00:04:57,210 --> 00:04:59,400 >> Bu yüzden tekrar yeni orta noktası hesaplayın. 109 00:04:59,400 --> 00:05:02,900 8 artı 10 2 9 bölü 18 olduğunu. 110 00:05:02,900 --> 00:05:05,074 Ve bu durumda, bak Hedef ortada olduğunu. 111 00:05:05,074 --> 00:05:06,740 Biz arıyoruz tam olarak ne bulundu. 112 00:05:06,740 --> 00:05:07,780 Durabiliriz. 113 00:05:07,780 --> 00:05:10,561 Biz başarıyla tamamlandı İkili arama. 114 00:05:10,561 --> 00:05:11,060 Pekala. 115 00:05:11,060 --> 00:05:13,930 Yani biz bu algoritma biliyoruz Hedef ise çalışır 116 00:05:13,930 --> 00:05:16,070 yere dizinin içinde. 117 00:05:16,070 --> 00:05:19,060 Bu algoritma çalışmaları ise mı Hedef dizide değil mi? 118 00:05:19,060 --> 00:05:20,810 Peki, bunu başlayalım Yine, bu sefer, 119 00:05:20,810 --> 00:05:23,380 en elemanı bakalım Görsel görebildiğimiz 16, 120 00:05:23,380 --> 00:05:25,620 Dizideki her yerde mevcut değildir. 121 00:05:25,620 --> 00:05:27,110 >> Başlangıç ​​noktası yine 0'dır. 122 00:05:27,110 --> 00:05:28,590 Bitiş noktası yine 14 olduğunu. 123 00:05:28,590 --> 00:05:32,490 Bunlar ilk endeksleri ve tam dizinin son elemanları. 124 00:05:32,490 --> 00:05:36,057 Ve biz süreç biz sadece üzerinden gidersiniz geçti yine 16 bulmaya çalışırken, 125 00:05:36,057 --> 00:05:39,140 Hatta görsel rağmen, biz zaten can Orada olmak için gitmiyor olduğunu söyle. 126 00:05:39,140 --> 00:05:43,450 Biz sadece emin bu algoritmayı yapmak istiyorum Aslında, halen bir şekilde çalışacak 127 00:05:43,450 --> 00:05:46,310 ve bizi bırakmaz sonsuz döngüye sıkışmış. 128 00:05:46,310 --> 00:05:48,190 >> Yani adım ilk ne var? 129 00:05:48,190 --> 00:05:50,230 Orta noktayı hesaplayın Geçerli dizinin. 130 00:05:50,230 --> 00:05:52,790 Orta neler var Mevcut dizinin? 131 00:05:52,790 --> 00:05:54,410 Peki, bu doğru, 7 değil mi? 132 00:05:54,410 --> 00:05:57,560 2 bölü 14 artı 0 7. 133 00:05:57,560 --> 00:05:59,280 Biz aradığınızı 15 mi? 134 00:05:59,280 --> 00:05:59,780 Hayır. 135 00:05:59,780 --> 00:06:02,930 Oldukça yakın, ama biz arıyoruz Bu biraz daha büyük bir değer. 136 00:06:02,930 --> 00:06:06,310 >> Yani biz o gidiyor biliyorum 15 solunda yerde olacak. 137 00:06:06,310 --> 00:06:08,540 Hedef daha büyüktür Ne orta içinde. 138 00:06:08,540 --> 00:06:12,450 Ve böylece biz yeni bir başlangıç ​​noktası olarak ayarlanmış Sadece orta sağında olacak. 139 00:06:12,450 --> 00:06:16,130 Orta noktası, yani henüz 7 yeni bir başlangıç ​​noktası 8 diyelim. 140 00:06:16,130 --> 00:06:18,130 Ve biz etkili Ne var Yine yapılan göz ardı edilir 141 00:06:18,130 --> 00:06:21,150 dizinin tüm sol yarısı. 142 00:06:21,150 --> 00:06:23,750 >> Şimdi, biz tekrar bir kez daha işlemeye. 143 00:06:23,750 --> 00:06:24,910 Yeni orta noktayı hesaplayın. 144 00:06:24,910 --> 00:06:29,350 8 artı 14 2 11 olduğu bölü 22 olduğunu. 145 00:06:29,350 --> 00:06:31,060 Biz aradığınızı 23 mi? 146 00:06:31,060 --> 00:06:31,870 Ne yazık ki hayır. 147 00:06:31,870 --> 00:06:34,930 Biz bir değere arıyoruz Bu az 23 olduğunu. 148 00:06:34,930 --> 00:06:37,850 Ve böylece bu durumda, biz gidiyoruz bitiş noktasını değiştirmek için adil olmak için 149 00:06:37,850 --> 00:06:40,035 Geçerli orta sol. 150 00:06:40,035 --> 00:06:43,440 Mevcut orta noktası 11 olan ve bu yüzden yeni bitiş noktasını ayarlamak gerekir 151 00:06:43,440 --> 00:06:46,980 Biz gitmek yakın zaman için 10 Bu süreçte. 152 00:06:46,980 --> 00:06:48,660 >> Yine, biz tekrar sürecinden geçmesi. 153 00:06:48,660 --> 00:06:49,640 Orta noktayı hesaplayın. 154 00:06:49,640 --> 00:06:53,100 2 ile bölünmesiyle 8 artı 10 9'dur. 155 00:06:53,100 --> 00:06:54,750 Biz aradığınızı 19 mi? 156 00:06:54,750 --> 00:06:55,500 Ne yazık ki hayır. 157 00:06:55,500 --> 00:06:58,050 Biz hala arıyoruz daha küçük bir sayı. 158 00:06:58,050 --> 00:07:02,060 Yani biz bitiş noktası bu kez değiştireceğiz Sadece orta solunda olmak. 159 00:07:02,060 --> 00:07:05,532 Orta, şu anda 9 yani bitiş noktası 8 olacak. 160 00:07:05,532 --> 00:07:07,920 Ve şimdi, biz sadece arıyoruz Tek bir eleman dizisi de. 161 00:07:07,920 --> 00:07:10,250 >> Bu dizinin orta noktası nedir? 162 00:07:10,250 --> 00:07:13,459 Eh, o, 8 başlar 8 de biter, orta noktası 8'dir. 163 00:07:13,459 --> 00:07:14,750 Biz aradığınızı mı? 164 00:07:14,750 --> 00:07:16,339 Biz 17 arıyorsunuz? 165 00:07:16,339 --> 00:07:17,380 Hayır, biz 16 arıyoruz. 166 00:07:17,380 --> 00:07:20,160 O dizide varsa Yani, bir yerde bulunması gerekir 167 00:07:20,160 --> 00:07:21,935 Şu anda nerede solunda. 168 00:07:21,935 --> 00:07:23,060 Peki ne yapacaksınız? 169 00:07:23,060 --> 00:07:26,610 Peki, biz sadece olmak için bitiş noktasını ayarlamak gerekir Geçerli orta sol. 170 00:07:26,610 --> 00:07:29,055 Yani biz 7 bitiş noktasını değiştirmek gerekir. 171 00:07:29,055 --> 00:07:32,120 Eğer sadece ne görüyor musun olsa da, burada ne oldu? 172 00:07:32,120 --> 00:07:33,370 Şimdi buraya bak. 173 00:07:33,370 --> 00:07:35,970 >> Başlat şimdi sonuna daha büyüktür. 174 00:07:35,970 --> 00:07:39,620 Etkin bir şekilde, iki ucu Bizim dizi geçti, 175 00:07:39,620 --> 00:07:42,252 ve başlangıç ​​noktasıdır Şimdi son noktadan sonra. 176 00:07:42,252 --> 00:07:43,960 Eh, o değil Doğru, hiçbir mantıklı? 177 00:07:43,960 --> 00:07:47,960 Peki şimdi ne söyleyebiliriz biz ise 0 boyutunda bir alt dizisi vardır. 178 00:07:47,960 --> 00:07:50,110 Ve bir kez biz aldık ediyoruz Bu nokta, biz şimdi can 179 00:07:50,110 --> 00:07:53,940 Bu eleman garanti 16 dizide mevcut değildir, 180 00:07:53,940 --> 00:07:56,280 Başlangıç ​​noktasında çünkü ve bitiş noktası geçti. 181 00:07:56,280 --> 00:07:58,340 Ve böylece yok. 182 00:07:58,340 --> 00:08:01,340 Şimdi, bu hafif olduğunu fark başlangıç ​​noktası ve sonu farklı 183 00:08:01,340 --> 00:08:02,900 aynı olan etmektedir. 184 00:08:02,900 --> 00:08:05,030 Biz seyir olsaydı 17 için, bu olurdu 185 00:08:05,030 --> 00:08:08,870 dizi ve başlangıç ​​noktası olmuştur Bu son yinelemenin ve bitiş noktası 186 00:08:08,870 --> 00:08:11,820 Bu noktalar geçti önce, Biz orada 17 bulurdum. 187 00:08:11,820 --> 00:08:15,510 Onlar biz o geçerken sadece var eleman yok garanti 188 00:08:15,510 --> 00:08:17,180 dizide mevcuttur. 189 00:08:17,180 --> 00:08:20,260 >> Yani çok az atalım Lineer arama daha adım. 190 00:08:20,260 --> 00:08:23,250 En kötü senaryoya göre, biz n öğelerin listesini bölmek 191 00:08:23,250 --> 00:08:27,770 defalarca yarısında, hedef bulmak için ya çünkü hedef elemanı 192 00:08:27,770 --> 00:08:33,110 Son bir yerde olacak bölünme, ya da hiç yoktur. 193 00:08:33,110 --> 00:08:37,830 En kötü durumda, bu yüzden biz var biliyor musunuz array-- ayrılalım? 194 00:08:37,830 --> 00:08:40,510 N kez Log; biz Sorunu kesmek zorunda 195 00:08:40,510 --> 00:08:42,610 kez yarım belirli bir sayıda. 196 00:08:42,610 --> 00:08:45,160 Kez bu sayı günlük n. 197 00:08:45,160 --> 00:08:46,510 >> En iyi senaryo nedir? 198 00:08:46,510 --> 00:08:48,899 Peki, ilk kez orta noktayı hesaplamak 199 00:08:48,899 --> 00:08:50,190 biz aradığınızı bulacaksınız. 200 00:08:50,190 --> 00:08:52,150 Önceki tüm olarak İkili arama örnekler 201 00:08:52,150 --> 00:08:55,489 Biz eğer biz sadece üzerinde gittin elemanı 15 arıyordum, 202 00:08:55,489 --> 00:08:57,030 biz hemen bulurdum. 203 00:08:57,030 --> 00:08:58,321 Bu çok başında oldu. 204 00:08:58,321 --> 00:09:01,200 Bu orta noktası oldu bir bölünme de ilk girişimi 205 00:09:01,200 --> 00:09:03,950 İkili arama bir bölümü. 206 00:09:03,950 --> 00:09:06,350 >> Ve böylece en kötü durum, ikili arama çalışır 207 00:09:06,350 --> 00:09:11,580 önemli ölçüde daha iyidir günlük n içinde En kötü durumda doğrusal arama, daha. 208 00:09:11,580 --> 00:09:16,210 En iyi durumda, ikili arama 1 omega çalışır. 209 00:09:16,210 --> 00:09:18,990 Yani ikili arama bir çok şey var Lineer arama daha iyi, 210 00:09:18,990 --> 00:09:23,270 ama süreci ile uğraşmak zorunda yapabilirsiniz ilk önce dizinizi sıralama 211 00:09:23,270 --> 00:09:26,140 İkili arama gücünü kaldıraç. 212 00:09:26,140 --> 00:09:27,130 >> Ben Doug Lloyd değilim. 213 00:09:27,130 --> 00:09:29,470 Bu CS 50. 214 00:09:29,470 --> 00:09:31,070