[MÜZİK OYUN] 

Doug LLOYD: Pekala. Yani ikili arama bir olduğunu Kullanabileceğimiz algoritma Bir dizinin içinde bir unsuru bulmak için. Doğrusal arama aksine, gerektiren bir özel durum, önceden yerine getirilmesi ama çok daha verimli, eğer var durum olduğunu, aslında, bir araya geldi. 

Yani fikir burada ne var? o böl ve fethet var. Biz boyutunu küçültmek istiyorum Yarım her zaman arama alanı Bir hedef numarasını bulmak için. Bu nerede durumdur olsa da, devreye giriyor. Biz sadece gücünü kullanabiliyorlar elementlerin ortadan yarısı Hatta bakmadan Onları dizi sıralanır eğer. 

Tam bir karışım kadar ise, biz sadece yandan dışarı olamaz Çünkü, elemanların yarısı atmak biz atarak biliyorum bilmiyorum. Ama dizi sıralanır eğer biz yapabilir çünkü biz o her şeyi biliyor Şu anda nerede sol daha düşük olmalıdır değer şu anda konum. Ve her şey için Nerede doğru değerinden daha büyük olmalıdır Şu anda bakıyoruz. 

Peki pseudocode ne İkili arama için adımlar? Biz gelene kadar bu işlemi tekrarlayın dizi ya, biz aracılığıyla ilerlerken, alt diziler, küçük parçalar Orijinal dizinin boyutu 0 olduğunu. Orta noktayı hesaplayın Geçerli alt dizinin. 

Aradığınız bir değerse Dizinin bu elemanın, dur. Buldun. Bu harika. Aksi takdirde, hedef ise, ortasında ne daha az, bu yüzden değeri eğer arıyoruz için biz ne görmek daha düşüktür Yine bu işlemi tekrarlayın, ancak Bunun yerine, bitiş noktasını değiştirmek Orijinal olma tam bir dizi tamamlamak, Sadece sola olmak nerede biz sadece baktı. 

Biz, orta çok yüksek olduğunu biliyordu veya hedef ortadan daha az ve bu nedenle, bulunmalıdır bunun ise , tüm dizide var yerde orta sol. Ve böylece biz dizi set edeceğiz Sadece sola yeri yeni son noktası olarak orta evi. Bunun aksine, hedef ise, ortasında ne büyüktür, biz tam aynı şeyi süreç, ancak bunun yerine biz olmak üzere başlangıç ​​noktasını değiştirmek Sadece orta sağında biz sadece hesapladı. Ve sonra, biz tekrar işlemine başlamak. 

En Tamam, bu görselleştirmek edelim? Yani gidiş ve burada bir çok şey var, ama burada 15 elemanlı bir dizi var. Ve biz takip için gidiyoruz çok daha fazla şeyler bu sefer. Yani doğrusal arama, biz Sadece bir hedefe hakkında bakmakta. Ama bu sefer biz istiyoruz biz nerede umurumda bakmak için başlangıç, nerede biz arıyoruz duruyoruz, ve orta ne Geçerli dizinin. Yani burada biz ikili arama ile gitmek. Biz hoş çok iyi gitmek, haklısın? Ben sadece aşağı koymak için gidiyorum endeksleri bir dizi aşağıda. Bu temelde sadece ne unsurdur Dizinin bahsediyoruz. Doğrusal arama, biz biz mademki, bakım Kaç bilmeniz gerekir Biz yineleme konum elemanları, ama biz aslında umurumda değil eleman şu anda bakıyoruz. İkili arama, biz bunu. Ve böylece bu sadece vardır Orada biraz rehber olarak. 

Bu yüzden, doğru başlayabiliriz? Peki, tam olarak değil. Ne dediğimi hatırlamıyorum İkili arama hakkında? Biz bunu yapamaz Başka ayrımı yapılmamış diğer dizi veya biz garanti değil Belirli öğeleri veya değerler değil Yanlışlıkla olmak atılan zaman biz sadece Dizinin yarısını görmezden karar verirler. 

Yani ikili arama ile bir adım Eğer sıralanmış dizi olması gerekir. Ve sıralama birini kullanabilirsiniz biz konuştuk algoritmalar Bu pozisyona almak için. Yani şimdi biz bir pozisyonda nerede konum Biz ikili arama yapabilirsiniz. 

Öyleyse işlemi yineleyin edelim adım adım ve tutmak Biz giderken neler olup bittiğini izlemek. Bu yüzden ilk biz hesaplamak yapmanız gereken Geçerli dizinin orta. Peki, biz ilk biz sen söyleyeceğim tüm değeri 19 arıyorum. Biz sayı 19 bulmaya çalışıyoruz. Bu ilk elemanı Dizi, endeks sıfır yer almaktadır ve bu son elemanı Dizi indeksi 14 yer almaktadır. Ve bu yüzden bu başlangıç ​​ve bitiş arayacağım. 

Bu yüzden orta noktayı göre hesaplamak 0 artı 2 bölü 14 eklenmesi; oldukça basit orta. Ve biz söyleyebiliriz orta noktası artık 7'dir. Yani 15 Aradığımız nedir? Hayır değil. Biz 19 arıyoruz. Ama biz 19 daha fazla olduğunu biliyoruz Biz ortada bulunan olandan. 

Yani biz ne yapabilirim Başlangıç ​​noktasını değiştirmek Sadece sağ olmak orta ve süreci tekrarlayın. Biz bunu yaparken, biz şimdi söylemek Yeni bir başlangıç ​​noktası dizisi yeri 8'dir. Ne biz etkili yaptık olduğunu 15 sol göz ardı her şeyi. Biz yarısını ortadan kaldırmış olduk Sorunun, ve şimdi, Bunun yerine aramak zorunda Bizim dizide üzerinde 15 elemanları, biz sadece 7 üzerinde aramak zorunda. Yani 8 yeni bir başlangıç ​​noktasıdır. 14 hala son noktasıdır. 

Ve şimdi, biz yine bu üzerine gitmek. Yeni orta noktayı hesaplar. 8 artı 14 2 11 olduğu bölü 22 olduğunu. Bu bizim aradığımız şey mi? Hayır değil. Biz bu değeri arıyorsanız biz sadece ne bulduğumuz daha az. Bu yüzden tekrar gidiyoruz Tekrar süreci. Biz son noktayı değiştirmek için gidiyoruz Sadece orta solunda olacak. Yani yeni uç nokta 10 olur. Ve şimdi, bu sadece bir parçası Dizi biz aracılığıyla sıralamak zorunda. Yani biz şimdi ortadan kaldırdık 15 elemanları 12. Biz biliyoruz 19 eğer dizide olup, bu elemanı arasında bir yerde bulunmalıdır 8 sayısı ve eleman sayısı 10. 

Bu yüzden tekrar yeni orta noktası hesaplayın. 8 artı 10 2 9 bölü 18 olduğunu. Ve bu durumda, bak Hedef ortada olduğunu. Biz arıyoruz tam olarak ne bulundu. Durabiliriz. Biz başarıyla tamamlandı İkili arama. Pekala. Yani biz bu algoritma biliyoruz Hedef ise çalışır yere dizinin içinde. Bu algoritma çalışmaları ise mı Hedef dizide değil mi? Peki, bunu başlayalım Yine, bu sefer, en elemanı bakalım Görsel görebildiğimiz 16, Dizideki her yerde mevcut değildir. 

Başlangıç ​​noktası yine 0'dır. Bitiş noktası yine 14 olduğunu. Bunlar ilk endeksleri ve tam dizinin son elemanları. Ve biz süreç biz sadece üzerinden gidersiniz geçti yine 16 bulmaya çalışırken, Hatta görsel rağmen, biz zaten can Orada olmak için gitmiyor olduğunu söyle. Biz sadece emin bu algoritmayı yapmak istiyorum Aslında, halen bir şekilde çalışacak ve bizi bırakmaz sonsuz döngüye sıkışmış. 

Yani adım ilk ne var? Orta noktayı hesaplayın Geçerli dizinin. Orta neler var Mevcut dizinin? Peki, bu doğru, 7 değil mi? 2 bölü 14 artı 0 7. Biz aradığınızı 15 mi? Hayır. Oldukça yakın, ama biz arıyoruz Bu biraz daha büyük bir değer. 

Yani biz o gidiyor biliyorum 15 solunda yerde olacak. Hedef daha büyüktür Ne orta içinde. Ve böylece biz yeni bir başlangıç ​​noktası olarak ayarlanmış Sadece orta sağında olacak. Orta noktası, yani henüz 7 yeni bir başlangıç ​​noktası 8 diyelim. Ve biz etkili Ne var Yine yapılan göz ardı edilir dizinin tüm sol yarısı. 

Şimdi, biz tekrar bir kez daha işlemeye. Yeni orta noktayı hesaplayın. 8 artı 14 2 11 olduğu bölü 22 olduğunu. Biz aradığınızı 23 mi? Ne yazık ki hayır. Biz bir değere arıyoruz Bu az 23 olduğunu. Ve böylece bu durumda, biz gidiyoruz bitiş noktasını değiştirmek için adil olmak için Geçerli orta sol. Mevcut orta noktası 11 olan ve bu yüzden yeni bitiş noktasını ayarlamak gerekir Biz gitmek yakın zaman için 10 Bu süreçte. 

Yine, biz tekrar sürecinden geçmesi. Orta noktayı hesaplayın. 2 ile bölünmesiyle 8 artı 10 9'dur. Biz aradığınızı 19 mi? Ne yazık ki hayır. Biz hala arıyoruz daha küçük bir sayı. Yani biz bitiş noktası bu kez değiştireceğiz Sadece orta solunda olmak. Orta, şu anda 9 yani bitiş noktası 8 olacak. Ve şimdi, biz sadece arıyoruz Tek bir eleman dizisi de. 

Bu dizinin orta noktası nedir? Eh, o, 8 başlar 8 de biter, orta noktası 8'dir. Biz aradığınızı mı? Biz 17 arıyorsunuz? Hayır, biz 16 arıyoruz. O dizide varsa Yani, bir yerde bulunması gerekir Şu anda nerede solunda. Peki ne yapacaksınız? Peki, biz sadece olmak için bitiş noktasını ayarlamak gerekir Geçerli orta sol. Yani biz 7 bitiş noktasını değiştirmek gerekir. Eğer sadece ne görüyor musun olsa da, burada ne oldu? Şimdi buraya bak. 

Başlat şimdi sonuna daha büyüktür. Etkin bir şekilde, iki ucu Bizim dizi geçti, ve başlangıç ​​noktasıdır Şimdi son noktadan sonra. Eh, o değil Doğru, hiçbir mantıklı? Peki şimdi ne söyleyebiliriz biz ise 0 boyutunda bir alt dizisi vardır. Ve bir kez biz aldık ediyoruz Bu nokta, biz şimdi can Bu eleman garanti 16 dizide mevcut değildir, Başlangıç ​​noktasında çünkü ve bitiş noktası geçti. Ve böylece yok. Şimdi, bu hafif olduğunu fark başlangıç ​​noktası ve sonu farklı aynı olan etmektedir. Biz seyir olsaydı 17 için, bu olurdu dizi ve başlangıç ​​noktası olmuştur Bu son yinelemenin ve bitiş noktası Bu noktalar geçti önce, Biz orada 17 bulurdum. Onlar biz o geçerken sadece var eleman yok garanti dizide mevcuttur. 

Yani çok az atalım Lineer arama daha adım. En kötü senaryoya göre, biz n öğelerin listesini bölmek defalarca yarısında, hedef bulmak için ya çünkü hedef elemanı Son bir yerde olacak bölünme, ya da hiç yoktur. En kötü durumda, bu yüzden biz var biliyor musunuz array-- ayrılalım? N kez Log; biz Sorunu kesmek zorunda kez yarım belirli bir sayıda. Kez bu sayı günlük n. 

En iyi senaryo nedir? Peki, ilk kez orta noktayı hesaplamak biz aradığınızı bulacaksınız. Önceki tüm olarak İkili arama örnekler Biz eğer biz sadece üzerinde gittin elemanı 15 arıyordum, biz hemen bulurdum. Bu çok başında oldu. Bu orta noktası oldu bir bölünme de ilk girişimi İkili arama bir bölümü. 

Ve böylece en kötü durum, ikili arama çalışır önemli ölçüde daha iyidir günlük n içinde En kötü durumda doğrusal arama, daha. En iyi durumda, ikili arama 1 omega çalışır. Yani ikili arama bir çok şey var Lineer arama daha iyi, ama süreci ile uğraşmak zorunda yapabilirsiniz ilk önce dizinizi sıralama İkili arama gücünü kaldıraç. 

Ben Doug Lloyd değilim. Bu CS 50.