[Bermain muzik] DOUG LLOYD: Baiklah. Jadi carian binari adalah algoritma kita boleh menggunakan untuk mencari satu elemen dalam array. Tidak seperti carian linear, ia memerlukan syarat khas dipenuhi terlebih dahulu, tetapi ia begitu jauh lebih efisien jika bahawa keadaan adalah, sebenarnya, dipenuhi. Jadi apa idea di sini? ia pecah dan perintah. Kami mahu mengurangkan saiz kawasan carian dengan separuh setiap kali untuk mencari beberapa sasaran. Ini adalah di mana syarat datang ke dalam bermain, walaupun. Kita hanya boleh memanfaatkan kuasa menghapuskan separuh daripada unsur-unsur tanpa melihat mereka jika array disusun. Jika ia merupakan satu campuran lengkap up, kita tidak boleh hanya keluar dari tangan membuang separuh daripada unsur-unsur, kerana kita tidak tahu apa yang kita membuang. Tetapi jika lokasi itu disusun, kita boleh berbuat demikian, kerana kita tahu bahawa segala-galanya kepada kiri di mana kita masa ini mesti lebih rendah daripada nilai kita pada masa ini. Dan segala-galanya kepada kanan di mana kita berada mesti lebih besar daripada nilai kami sedang melihat. Jadi apa pseudokod langkah-langkah untuk carian binari? Kami mengulangi proses ini sehingga pelbagai atau, seperti yang kita meneruskan melalui, array sub, bahagian yang lebih kecil daripada pelbagai asal, adalah saiz 0. Kira titik tengah sub lokasi semasa. Jika nilai yang anda cari adalah dalam elemen array, berhenti. Anda menjumpainya. Itu yang besar. Jika tidak, jika sasaran adalah kurang daripada apa yang di tengah-tengah, jadi jika nilai kita sedang adalah lebih rendah daripada apa yang kita lihat, mengulangi proses ini sekali lagi, tetapi menukar titik akhir, dan bukannya menjadi asal melengkapkan pelbagai penuh, menjadi hanya ke kiri di mana kita hanya melihat. Kami tahu bahawa tengah-tengah adalah terlalu tinggi, atau sasaran itu kurang daripada tengah-tengah, dan oleh itu mesti wujud, jika ia wujud sama sekali dalam array, di suatu tempat di sebelah kiri titik tengah. Dan dengan itu kita akan menetapkan array lokasi hanya ke kiri daripada titik tengah sebagai titik akhir baru. Sebaliknya, jika sasaran adalah lebih besar daripada apa yang di tengah-tengah, kami melakukan yang sama proses, tetapi sebaliknya kita menukar titik permulaan untuk menjadi hanya di sebelah kanan titik tengah kita hanya dikira. Dan kemudian, kita memulakan proses lagi. Mari kita menggambarkan hal ini, OK? Jadi ada banyak berlaku dan di sini, tetapi di sini adalah pelbagai daripada 15 elemen. Dan kita akan dapat mengesan daripada banyak lagi barangan masa ini. Jadi, dalam carian linear, kami hanya mengambil berat tentang sasaran. Tetapi kali ini kita mahu mengambil berat tentang di mana kita mula kelihatan, di mana kita berhenti mencari, dan apa yang titik tengah array semasa. Jadi di sini kita pergi dengan carian binari. Kami cukup banyak yang baik untuk pergi, bukan? Saya hanya akan meletakkan bawah sini satu set indeks. Ini adalah pada dasarnya apa unsur array kita berbicara tentang. Dengan carian linear, kita peduli, bukankah kita perlu tahu berapa banyak unsur-unsur yang kita iterating ke atas, tetapi kita tidak benar-benar peduli apa elemen kami sedang melihat. Dalam mencari binari, kita lakukan. Dan supaya orang-orang yang hanya ada sebagai panduan sedikit. Oleh itu, kita boleh mula, bukan? Well, tidak cukup. Ingat apa yang saya katakan tentang carian binari? Kita tidak boleh melakukannya pada lokasi terisih atau yang lain, kami tidak memberi jaminan bahawa unsur-unsur atau nilai-nilai tertentu tidak tidak sengaja dibuang apabila kita hanya memutuskan untuk mengabaikan separuh daripada array. Jadi langkah satu dengan carian binari adalah anda mesti mempunyai lokasi disusun. Dan anda boleh menggunakan mana-mana pengasingan algoritma kita telah bercakap tentang untuk mendapatkan anda untuk kedudukan itu. Oleh sebab itu, kita berada dalam kedudukan di mana kita boleh melakukan carian binari. Jadi mari kita mengulangi proses tersebut langkah demi langkah dan mengesan apa yang berlaku seperti yang kita pergi. Oleh itu, pertama yang perlu kita lakukan ialah mengira titik tengah lokasi semasa. Baiklah, kami akan mengatakan bahawa kita berada, pertama semua, mencari nilai 19. Kami cuba untuk mencari bilangan 19. Elemen pertama ini lokasi terletak di indeks sifar, dan elemen terakhir ini lokasi terletak di indeks 14. Dan dengan itu kita akan memanggil mereka yang mula dan akhir. Oleh itu, kita mengira titik tengah oleh menambah 0 tambah 14 dibahagikan dengan 2; titik tengah agak mudah. Dan kita boleh mengatakan bahawa titik tengah itu kini 7. Begitu juga 15 apa yang kami cari? Tidak. Kami sedang mencari 19. Tetapi kita tahu bahawa 19 adalah lebih besar daripada apa yang kita dapati di tengah-tengah. Jadi apa yang kita boleh lakukan ialah menukar titik permulaan menjadi hanya di sebelah kanan yang titik tengah, dan mengulangi proses tersebut lagi. Dan apabila kita berbuat demikian, kita sekarang mengatakan titik permulaan yang baru adalah lokasi mudah 8. Apa yang kita telah dilakukan dengan berkesan adalah semua yang diabaikan di sebelah kiri 15. Kami telah dihapuskan separuh masalah ini, dan kini, daripada harus mencari lebih 15 elemen dalam array kita, kita hanya perlu mencari lebih 7. Jadi 8 adalah titik permulaan yang baru. 14 masih titik akhir. Dan sekarang, kami akan ke ini lagi. Kami mengira titik tengah baru. 8 campur 14 adalah 22, dibahagikan dengan 2 adalah 11. Adakah ini yang kita cari? Tidak. Kami sedang mencari satu nilai yang kurang daripada apa yang kita hanya dijumpai. Jadi, kita akan mengulangi proses sekali lagi. Kami akan menukar titik akhir untuk hanya di sebelah kiri titik tengah. Jadi titik akhir baru menjadi 10. Dan sekarang, itu hanya sebahagian daripada array kita perlu menyusun melalui. Oleh itu, kita kini telah dihapuskan 12 daripada 15 elemen. Kita tahu bahawa jika 19 wujud dalam array, ia mesti wujud di suatu tempat antara elemen nombor 8 dan unsur nombor 10. Oleh itu, kita mengira titik tengah baru lagi. 8 campur 10 adalah 18, dibahagikan dengan 2 adalah 9. Dan dalam kes ini, melihat, yang sasaran adalah di tengah-tengah. Kami mendapati apa yang kita cari. Kita boleh berhenti. Kami berjaya menamatkan carian binari. Baiklah. Jadi kita tahu algoritma ini berfungsi jika sasaran adalah suatu tempat di dalam array. Adakah ini kerja algoritma jika sasaran itu tidak berada dalam array? Nah, mari kita memulakannya sekali lagi, dan kali ini, mari kita lihat untuk elemen 16, yang secara visual kita dapat melihat tidak wujud mana-mana sahaja dalam array. Titik permulaan sekali lagi 0. Titik akhir sekali lagi 14. Mereka adalah indeks yang pertama dan elemen terakhir array lengkap. Dan kita akan melalui proses yang kita hanya lalui lagi, cuba untuk mencari 16, walaupun cacat, kita boleh sudah memberitahu bahawa ia tidak akan berada di sana. Kami hanya mahu memastikan algoritma ini akan, sebenarnya, masih bekerja dalam beberapa cara dan bukan hanya meninggalkan kita terperangkap dalam gelung tak terhingga. Jadi apa langkah pertama? Kira titik tengah array semasa. Apakah titik tengah array semasa? Nah, ia adalah 7, bukan? 14 tambah 0 dibahagikan dengan 2 adalah 7. 15 apa yang kami cari? No. Ia agak rapat, tetapi kami tidak sabar- untuk nilai yang lebih besar sedikit daripada itu. Jadi kita tahu bahawa ia akan menjadi tempat untuk sebelah kiri 15. Sasaran adalah lebih besar daripada apa yang di titik tengah. Dan dengan itu kita menetapkan titik permulaan yang baru untuk hanya di sebelah kanan tengah-tengah. Titik tengah itu kini 7, jadi katakan titik permulaan baru adalah 8. Dan apa yang kita ada dengan berkesan dilakukan sekali lagi diabaikan separuh kiri keseluruhan array. Sekarang, kita mengulangi memproses sekali lagi. Kira titik tengah baru. 8 campur 14 adalah 22, dibahagikan dengan 2 adalah 11. Adalah 23 apa yang kami cari? Malangnya tidak. Kami sedang mencari nilai yang yang kurang daripada 23. Dan sebagainya dalam kes ini, kita akan untuk menukar titik akhir menjadi hanya di sebelah kiri titik tengah semasa. Titik tengah semasa adalah 11, dan jadi kita akan menetapkan titik akhir baru untuk masa yang akan datang kita pergi melalui proses ini hingga 10. Sekali lagi, kita melalui proses lagi. Kira titik tengah. 8 ditambah 10 dibahagikan dengan 2 adalah 9. Adalah 19 apa yang kami cari? Malangnya tidak. Kami masih mencari bilangan yang kurang daripada itu. Oleh itu, kita akan menukar titik akhir masa ini menjadi hanya di sebelah kiri titik tengah. Titik tengah itu kini 9, jadi titik akhir akan 8. Dan kini, kami hanya mencari di pelbagai elemen. Apakah titik tengah pelbagai ini? Nah, ia bermula pada 8, ia berakhir pada 8, titik tengah adalah 8. Adakah itu yang kita cari? Adakah kita mencari 17? Tidak, kami mencari 16. Jadi, jika ia wujud dalam array, ia mesti wujud di suatu tempat sebelah kiri di mana kita kini berada. Jadi apa yang kita akan lakukan? Baiklah, kami akan menetapkan titik akhirnya menjadi hanya di sebelah kiri titik tengah semasa. Oleh itu, kita akan menukar titik akhir hingga 7. Adakah anda melihat apa yang hanya yang berlaku di sini, walaupun? Lihatlah di sini sekarang. Mula kini lebih besar daripada akhir. Berkesan, kedua-dua hujung pelbagai kami telah berpindah, dan titik permulaan adalah kini selepas titik akhir. Nah, yang tidak masuk akal, bukan? Oleh sebab itu, apa yang kita boleh katakan ialah kita mempunyai pelbagai sub saiz 0. Dan apabila kita mendapat ke ketika ini, kita kini boleh menjamin elemen yang 16 tidak wujud dalam array, kerana titik permulaan dan titik akhir telah melintasi. Dan oleh itu tidak ada. Sekarang, perhatikan bahawa ini adalah sedikit berbeza daripada titik mula dan akhir menunjukkan adalah sama. Jika kita telah mencari 17, ia akan mempunyai berada dalam array, dan titik permulaan dan titik akhir yang lelaran lalu sebelum mata tersebut melintasi, kita akan mendapati 17 di sana. Ia hanya apabila mereka melintas yang kita boleh menjamin bahawa unsur tidak wujud dalam array. Jadi mari kita mengambil masa yang lebih sedikit langkah-langkah daripada carian linear. Dalam kes yang teruk, kami terpaksa berpecah senarai n unsur berulang kali pada separuh untuk mencari sasaran, sama ada kerana elemen sasaran akan menjadi suatu tempat di lepas bahagian, atau ia tidak wujud sama sekali. Jadi dalam kes yang paling teruk, kita perlu berpecah array-- yang anda tahu? Log n masa; kita perlu memotong masalah dalam setengah beberapa kali. Yang beberapa kali adalah log n. Apakah senario kes terbaik? Well, masa kita mula-mula mengira titik tengah, kita mencari apa yang kita cari. Dalam semua sebelumnya contoh pada carian binari kita baru sahaja pergi ke atas, jika kita mempunyai cari selama unsur 15, kita akan mendapati bahawa dengan segera. Itu adalah pada awal-awal. Itu adalah titik tengah percubaan pertama di perpecahan satu bahagian dalam carian binari. Jadi dengan yang paling teruk kes, carian binari berjalan dalam log n, harga yang jauh lebih baik daripada carian linear, dalam kes yang paling teruk. Dalam kes ini, binari carian berjalan dalam omega 1. Jadi carian binari adalah banyak lebih baik daripada carian linear, tetapi anda perlu berurusan dengan proses menyusun pelbagai anda terlebih dahulu sebelum anda boleh memanfaatkan kuasa carian binari. Saya Doug Lloyd. Ini adalah CS 50.