[Bermain muzik] ANDI PENG: Selamat datang ke minggu 3 bahagian. Terima kasih, anda semua, untuk semua yang datang ini masa mula awal hari ini. Kami telah mendapat yang baik, sedikit kumpulan intim hari ini. Jadi mudah-mudahan kita akan mendapat kemasan, mungkin, awal, sedikit awal hari ini. Begitu cepat, hanya beberapa pengumuman untuk agenda hari ini. Sebelum kita bermula, kami akan hanya pergi beberapa isu logistik ringkas, pset soalan, Debrief, perkara seperti itu. Dan kemudian kita akan digalakkan untuk menterjemah. Kami akan menggunakan penyahpepijat dipanggil GDB untuk mula membongkar kod kami, yang David dijelaskan dalam kuliah pada hari yang lain. Kami akan pergi ke atas empat jenis macam. Kami akan pergi ke atas mereka cukup cepat sejak mereka cukup rapi. Tetapi tahu bahawa semua slaid dan kod sumber sentiasa talian. Jadi berasa bebas, pada penelitian anda, untuk kembali dan kita lihat itu. Kami akan pergi melalui notasi asimptot, yang hanya cara yang mewah berkata "runtimes," di mana kita mempunyai O yang besar, yang David menjelaskan dalam kuliah. Dan kami juga mempunyai Omega, yang adalah runtime yang terikat lebih rendah. Dan kita akan bercakap sedikit lebih mendalam mengenai bagaimana mereka bekerja. Dan akhir sekali, kita akan pergi ke carian binari, kerana banyak yang sudah mengerling ke arah psets anda mungkin tahu bahawa itu adalah soalan yang dalam pset anda. Jadi, anda semua akan senang yang kami meliputi hari ini. Dan akhir sekali, setiap anda seksyen maklum balas, saya benar-benar meninggalkan kira-kira 15 minit pada akhir untuk hanya pergi logistik pset3, apa-apa soalan, mungkin sedikit panduan, jika anda akan, sebelum kita mula pengaturcaraan. Jadi mari kita cuba untuk mendapatkan melalui bahan yang cukup cepat. Dan kemudian kita boleh meluangkan sedikit masa mengambil lebih banyak soalan untuk pset. OKAY. Dengan cepat, jadi hanya beberapa pengumuman sebelum kita bermula hari ini. Pertama sekali, selamat datang untuk membuat melalui dua daripada psets anda. Saya mengambil lihat pada your-- yeah, mari kita mendapatkan satu pusingan tepukan untuk yang itu. Sebenarnya, saya benar-benar, benar-benar kagum. Saya digred pset pertama untuk anda semua minggu dan kali terakhir anda seorang lelaki lakukan yang luar biasa. Gaya adalah mengenai hal selain beberapa komen. Pastikan anda sentiasa mengulas kod anda. Tetapi psets anda berada di mata. Dan bertahan lama. Dan ia adalah baik untuk gred untuk melihat bahawa kamu semua meletakkan sebagai banyak usaha dalam gaya anda dan reka bentuk anda dalam kod anda yang kita ingin untuk anda lihat. Jadi, saya melewati terima kasih untuk yang lain daripada TA. Walau bagaimanapun terdapat beberapa soalan Debrief Saya hanya mahu pergi ke yang akan menjadikan kedua-dua hidup saya dan banyak yang lain TA 'hidup sedikit lebih mudah. Pertama sekali, saya dapati ini lalu week-- berapa ramai daripada anda telah berjalan check50 pada kod anda sebelum anda hantar? OKAY. Jadi semua orang harus lakukan check50, because-- yang secret-- kita benar-benar menjalankan check50 sebagai sebahagian daripada kebenaran kami skrip untuk menguji kod anda. Jadi, jika kod anda gagal check50, dalam semua kemungkinan, ia mungkin akan gagal mendaftar kita juga. Kadang-kadang anda semua mempunyai jawapan yang betul. Seperti, dalam tamak, beberapa anda mempunyai nombor yang betul, anda hanya mencetak beberapa perkara tambahan. Dan bahawa barangan tambahan sebenarnya gagal cek, kerana komputer tidak benar-benar tahu apa yang ia cari. Dan sebagainya ia hanya akan berjalan melalui, melihat bahawa output anda tidak sepadan dengan apa yang kita harapkan jawapan menjadi, dan menandakan ia adalah salah. Dan saya tahu yang berlaku di beberapa kes anda minggu ini. Jadi saya kembali dan secara manual digred semula kod semua orang. Pada masa akan datang walaupun, sila, sila pastikan bahawa anda menjalankan menyemak 50 pada kod anda. Oleh kerana ia adalah jenis sakit untuk TA untuk mempunyai untuk kembali dan secara manual Regrade setiap pset tunggal bagi setiap tunggal, misalnya sedikit terlepas. Jadi saya tidak mengambil kira apa-apa mata. Saya rasa saya mengambil kira mungkin satu atau dua untuk reka bentuk. Pada masa akan datang walaupun, jika anda gagal check50, mata akan diambil padang kerana kebenaran. Tambahan pula, psets adalah kerana hari Jumaat pada tengah hari. Saya fikir ada tujuh minit Tambahan masa lewat yang kita berikan anda. Penerbangan masa Harvard, mereka dibenarkan untuk tujuh minit lewat untuk segala-galanya. Jadi di sini di Yale, kami akan mematuhi itu juga. Tetapi cukup banyak, pada 00:07, jika pset anda tidak berada dalam, ia akan diingati sebagai lewat. Dan jadi sementara ia ditandakan sebagai-an, TA-- Saya masih akan penggredan psets anda. Oleh itu, anda masih akan melihat gred yang muncul. Walau bagaimanapun, tahu bahawa pada akhir semester, semua psets lewat hanya akan menjadi secara automatik menumpukan perhatian oleh komputer. Kami melakukan ini kerana dua sebab. Satu, kadang-kadang kita mendapatkan dimaafkan, seperti alasan dekan, kemudian bahawa saya tidak tahu tentang lagi. Oleh itu, kita suka untuk memastikan bahawa kami tidak penggredan segala-galanya hanya dalam kes, seperti, Saya hilang alasan yang dekan. Dan kedua, perlu fikiran, anda masih boleh menggugurkan satu Serangga yang mempunyai mata skop penuh. Dan supaya kita suka untuk gred semua psets anda hanya memastikan bahawa skop anda di sana dan anda cuba mereka. Jadi, walaupun ia lewat, anda akan masih mendapatkan kredit untuk mata skop, saya fikir. Jadi moral cerita ini adalah, membuat memastikan psets anda berada dalam pada masa. Dan jika mereka tidak berada di dalam masa, tahu bahawa ia bukan yang besar. Ya, sebelum saya bergerak ke atas, tidak sesiapa yang mempunyai sebarang pertanyaan mengenai maklum balas pset? Yeah. PENONTON: Adakah anda mengatakan bahawa kita boleh turun salah satu daripada psets? ANDI PENG: Ya. Jadi ada sembilan psets keseluruhan sepanjang semester. Dan jika anda mempunyai skop points-- supaya skop keadilan, cukup banyak, yang anda cuba yang masalah, anda meletakkan dalam masa, yang anda menunjukkan bahawa anda telah menunjukkan anda telah membaca spesifikasi. Itulah skop cukup banyak. Dan jika anda memenuhi mata skop, kita boleh turun serendah satu daripada skop penuh. Jadi itulah dalam kelebihan anda untuk melengkapkan dan cuba setiap pset. Walaupun upload-- jika tiada mereka bekerja, memuat naik mereka semua. Dan kemudian kita mudah-mudahan akan dapat memberi anda beberapa mata tersebut kembali. Sejuk. Apa-apa soalan lain? Yang besar. Kedua, pejabat hours-- beberapa nota ringkas mengenai waktu pejabat. Jadi pertama, datang awal minggu ini. Tiada siapa yang pernah di waktu pejabat pada hari Isnin. Christabel datang ke waktu pejabat, malam tadi. Ya, Christabel. Dan apa yang kita ada di pejabat jam malam tadi, Christabel? PENONTON: Kami mempunyai ais krim. ANDI PENG: Jadi, itu betul, kita mempunyai ais krim di waktu pejabat, malam tadi. Walaupun saya tidak boleh berjanji kepada anda bahawa kita akan mempunyai ais krim di waktu pejabat setiap minggu, apa yang boleh saya berjanji kepada anda adalah bahawa akan menjadi ketara pelajar yang lebih baik kepada nisbah TA. Seperti legit, ia seperti 3-1. Manakala, bezakan bahawa dengan Khamis, anda mempunyai kira-kira 150 benar-benar menekankan kanak-kanak dan tiada ais krim. Dan ia hanya tidak produktif untuk sesiapa sahaja. Jadi moral cerita itu, datang awal kepada waktu pejabat dan perkara-perkara yang baik akan berlaku. Juga, datang bersedia untuk bertanya soalan. Awak tahu? Tidak kira apa TA, saya berfikir, telah berkata, kita telah mendapat beberapa pelajar yang datang pada hari Khamis pada, seperti, 10:50 tidak membaca spec menjadi seperti membantu saya, membantu saya. Malangnya pada ketika itu, ada tidak banyak yang boleh kita lakukan untuk membantu anda. Oleh itu, sila datang awal minggu ini. Datang awal untuk waktu pejabat. Datang bersedia untuk bertanya soalan. Pastikan bahawa anda, sebagai seorang pelajar, adalah di mana anda perlu supaya TA boleh membimbing anda bersama-sama, iaitu apa waktu pejabat sepatutnya diperuntukkan untuk. Kedua, jadi saya tahu profesor suka untuk mengejutkan kita dengan ujian. Saya mempunyai seorang profesor mereka seperti, yo, dengan cara itu, ingat separuh penggal yang anda mempunyai Isnin depan. Ya, saya tidak tahu tentang separuh penggal itu. Jadi, saya akan menjadi yang TA yang mengingatkan anda semua kuiz yang 0-- kerana, anda tahu, kami CS. Sekarang kami telah tatasusunan dilakukan, anda akan mendapat mengapa ia kuiz 0, bukan kuiz 1, eh? OKAY. Oh, saya mendapat beberapa chuckles pada yang satu. OKAY. Jadi kuiz 0 akan menjadi 14 Okt jika anda berada dalam bahagian Isnin-Rabu dan 15 Oktober jika anda berada dalam bahagian Selasa-Khamis. Ini tidak terpakai bagi Pelawat di Harvard yang- saya rasa anda semua akan menjadi mengambil kuiz anda pada ke-14. Jadi ya, minggu depan, jika David, dalam kuliah, pergi, yeah, jadi kira-kira yang kuiz minggu depan, anda semua tidak akan terkejut kerana anda datang ke seksyen dan anda tahu bahawa anda kuiz 0 adalah dalam dua minggu. Dan kita akan mempunyai kajian sesi dan segala-galanya. Jadi tidak ada kebimbangan mengenai menjadi takut untuk itu. Sebarang soalan sebelum itu apa-apa soalan di semua isu-isu logistik mengenai, penggredan, waktu pejabat, bahagian-bahagian? Yeah. PENONTON: Jadi kuiz adalah akan menjadi semasa kuliah? ANDI PENG: Ya. Jadi kuiz, saya fikir, adalah 60 minit yang diperuntukkan dalam bahawa slot masa bahawa anda hanya akan mengambil di dalam dewan kuliah. Jadi anda tidak perlu datang dalam pada, seperti, rawak 07:00. Itu semua baik. Yeah. Sejuk. Baiklah. Oleh itu, kita akan memperkenalkan konsep kepada anda minggu ini bahawa Daud telah pun jenis daripada menyentuh dalam syarahan ini minggu lalu. Ia dipanggil GDB. Dan berapa ramai daripada anda, manakala di semasa menulis psets anda, perasan butang besar yang mengatakan "Debug" pada bahagian atas IDE anda? OKAY. Oleh sebab itu kita benar-benar akan dapat mencungkil misteri apa butang yang benar-benar tidak. Dan saya jamin anda, ia adalah satu indah, perkara yang indah. Jadi sehingga kini, saya rasa telah ada dua perkara pelajar ini adalah pada lazimnya lakukan apabila debugging psets. Satu, mereka sama ada tambahkan printf () - jadi setiap beberapa baris, mereka menambah dalam printf () - oh, apa yang berubah-ubah ini? Oh, apa yang berubah-ubah ini sekarang-- dan anda jenis melihat perkembangan kod anda semasa jalanan. Atau kaedah kedua anak-anak lakukan adalah bahawa mereka hanya menulis segala-galanya dan kemudian pergi seperti ini pada akhir. Mudah-mudahan ia berfungsi. Saya jamin anda, GDB adalah lebih baik daripada kedua-dua mereka kaedah. Yeah. Jadi ini akan menjadi rakan baru anda yang terbaik. Kerana ia adalah satu perkara yang indah yang visual memaparkan kedua-dua apa kod anda lakukan pada satu titik tertentu dan juga apa yang semua anda pemboleh ubah yang dibawa, seperti apa nilai-nilai mereka, pada titik tertentu. Dan dengan cara ini, anda boleh benar-benar menetapkan titik putus dalam kod anda. Anda boleh berjalan melalui baris demi baris. Dan GDB hanya perlu untuk anda, dipaparkan untuk anda, apa semua pembolehubah anda adalah, apa yang mereka lakukan, apa yang berlaku di dalam kod. Dan dalam apa-apa cara, ia adalah lebih mudah untuk melihat apa yang berlaku bukannya printf-ing atau menulis kenyataan anda. Oleh itu, kita akan melakukan satu contoh ini kemudian. Jadi ini seolah-olah satu abstrak bit. Jangan bimbang, kami akan melakukan contoh. Dan sebagainya pada dasarnya, ketiga-tiga terbesar, Fungsi yang selalu digunakan yang anda perlukan dalam GDB adalah Seterusnya, Langkah ke atas, dan Masuklah ke butang. Saya akan menuju di sana, sebenarnya, sekarang. Jadi kalian semua dapat melihat bahawa atau saya perlu zum masuk sedikit? Di belakang, anda dapat melihat bahawa? Adakah saya perlu zum masuk? Cuma sedikit? OK, sejuk. Di sana kami pergi. OKAY. Jadi saya perlu, di sini, saya pelaksanaan bagi tamak. Dan manakala banyak kamu menulis tamak dalam gelung sementara form-- yang adalah cara yang boleh diterima untuk melakukan kitab itu satu lagi cara untuk melakukannya adalah dengan hanya membahagikan dalam modulo itu. Kerana anda boleh mempunyai anda nilai dan kemudian mempunyai baki anda. Dan kemudian anda boleh hanya menambah semua bersama-sama. Adakah logik apa yang saya lakukan di sini masuk akal untuk semua orang, sebelum kita bermula? Jenis? Sejuk. Yang besar. Ia adalah sekeping cantik seksi kod, saya akan berkata. Seperti saya katakan, Daud, syarahan, selepas beberapa ketika, anda semua akan mula melihat kod sebagai sesuatu yang indah. Dan kadang-kadang apabila anda melihat indah kod, ia seperti satu perasaan yang indah. Jadi bagaimanapun, manakala kod ini adalah sangat indah, ia tidak berfungsi dengan baik. Jadi mari kita berjalan check50 mengenai perkara ini. Semak 50 20-- oop. 2? Adakah pset2 itu? Yeah. Oh, pset1. OKAY. Oleh itu, kita menjalankan check50. Dan seperti yang anda semua boleh lihat di sini, ia gagal beberapa kes. Dan bagi sesetengah daripada anda, dalam proses menjalankan set masalah anda, anda seperti, ah, mengapa tidak ia bekerja. Mengapa ia bekerja untuk beberapa nilai tetapi tidak untuk orang lain? Nah, GDB akan membantu angka anda mengapa mereka input itu tidak berfungsi. OKAY. Jadi mari kita lihat, salah satu daripada cek saya gagal dalam check50 adalah nilai input 0.41. Jadi jawapan yang betul yang anda perlu mendapatkan ialah 4. Tetapi sebaliknya apa yang saya mencetak adalah 3-n, yang tidak betul. Jadi mari kita hanya menjalankan ini secara manual, hanya memastikan bahawa check50 bekerja. Mari kita buat ./greedy. Oops, saya perlu membuat tamak. Di sana kami pergi. Sekarang ./greedy. Berapa banyak yang berhutang? Mari kita buat 0.41. Dan yep, kita lihat di sini bahawa ia keluarkan 3 apabila jawapan yang betul, sebenarnya, perlu 4. Jadi mari kita masukkan GDB dan melihat bagaimana kita boleh pergi tentang cara menangani masalah ini. Jadi langkah pertama dalam sentiasa debugging kod anda adalah untuk menetapkan titik putus a, atau titik di mana anda mahu komputer atau penyahpepijat untuk mula melihat. Jadi, jika anda tidak benar-benar tahu apa masalah anda, biasanya, perkara yang biasa kita mahu lakukan adalah untuk menetapkan titik putus kami di utama. Jadi, jika anda semua boleh melihat ini butang merah di sana, yep, yang saya menetapkan Titik Henti untuk fungsi utama. Saya klik itu. Dan kemudian saya boleh naik ke butang Debug saya. Saya tekan butang itu. Biar saya zum keluar jika saya boleh. Di sana kami pergi. Jadi kita mempunyai, di sini, panel sebelah kanan. Saya minta maaf, lelaki di belakang, anda tidak boleh benar-benar melihat dengan sangat baik. Tetapi pada dasarnya, semua panel ini di lakukan yang mengesan kedua-dua yang diserlahkan talian, yang merupakan baris kod bahawa komputer sedang berjalan, dan juga semua pembolehubah anda di bawah ini. Jadi, anda telah mendapat sen, syiling, n, semua diisytiharkan perkara yang berbeza pada ketika ini. Jangan bimbang, kerana kita tidak benar-benar dimulakan mereka kepada mana-mana pemboleh ubah lagi. Jadi dalam komputer anda, anda komputer baru sahaja melihat, oh, 32767 adalah fungsi yang terakhir digunakan itu ruang ingatan dalam komputer saya. Dan supaya di mana sen pada masa ini. Tetapi tidak bahawa apabila anda menjalankan kod, ia harus menjadi dimulakan. Jadi mari kita pergi melalui, baris demi talian, apa yang berlaku di sini. OKAY. Jadi di sini adalah tiga butang yang saya hanya menjelaskan. Anda perlu Main, atau fungsi Run, butang, anda perlu Langkah butang ke atas, dan anda juga mempunyai Langkah ke butang. Dan pada dasarnya, ketiga-tiga mereka hanya pergi melalui kod anda dan melakukan perkara-perkara yang berbeza. Jadi biasanya, apabila anda debugging, kita tidak mahu hanya tekan Main, kerana Main hanya akan berjalan kod anda untuk akhir itu. Dan kemudian anda tidak akan benar-benar tahu apa masalah anda adalah melainkan jika anda menetapkan pelbagai titik putus. Jika anda menetapkan pelbagai titik putus, ia akan hanya secara automatik berjalan dari satu titik putus, ke depan, ke depan. Tetapi dalam kes ini kami telah hanya satu yang, kerana kita mahu bekerja cara kita dari atas turun ke bawah. Jadi, kita akan mengabaikan butang yang sekarang untuk tujuan program ini. Jadi Langkah alih fungsi hanya langkah-langkah ke atas setiap baris dan memberitahu anda apa komputer lakukan. Langkah ke dalam fungsi pergi ke dalam fungsi sebenar yang pada talian anda kod. Jadi, sebagai contoh, seperti printf (), iaitu fungsi, bukan? Jika saya mahu langkah fizikal ke dalam fungsi printf (), Saya benar-benar akan pergi ke dalam sekeping kod di mana printf () telah ditulis dan melihat apa yang sedang berlaku di sana. Tetapi biasanya, kita menganggap bahawa kod yang kami memberi anda berfungsi. Kami menganggap printf () bekerja. Kami menganggap bahawa GetInt () bekerja. Jadi tidak ada keperluan untuk melangkah ke fungsi-fungsi itu. Tetapi jika ada fungsi yang anda tulis sendiri yang anda mahu untuk memeriksa mengetahui apa yang berlaku, anda yang sanggup membuat ke dalam fungsi itu. Jadi sekarang kita hanya akan melangkah ini sekeping kod. Jadi mari kita lihat. Oh, cetak, "Oh hai, bagaimana banyak perubahan berhutang? " Kami tidak peduli. Kita tahu bahawa bekerja, jadi kami melangkah ke atasnya. Jadi n, yang terapung kami yang kami telah initialized-- atau declared-- sehingga di bahagian atas, kami kini menyamai bahawa untuk GetFloat (). Jadi mari kita melangkah itu. Dan kita lihat di bawah di sini, program ini adalah mendorong saya untuk input nilai. Jadi mari kita input nilai yang kami mahu untuk menguji di sini, iaitu 0.41. Yang besar. Jadi sekarang n-- adakah anda seorang lelaki melihat di sini, pada bottom-- ia stored-- kerana kita tidak bulat lagi, ia disimpan dalam gergasi seperti ini apungan yang ,4099999996, yang cukup dekat dengan kami tujuan, sekarang, untuk 0.41. Dan kemudian kita akan melihat di kemudian hari, seperti yang kita terus melangkah lebih program ini, selepas sini, n telah menjadi bulat dan sen menjadi 41. Yang besar. Jadi kita tahu bahawa kerja pembundaran kita. Kita tahu bahawa kita mempunyai nombor yang betul sen, jadi kita tahu bahawa itulah tidak benar-benar masalah. Oleh itu, kita terus melangkah di dalam program ini. Kami pergi di sini. Dan sebagainya selepas baris kod ini, kita akan melihat bagaimana banyak pihak yang kita ada. Kami melangkah. Dan kamu melihat kita, sebenarnya, mempunyai satu suku kerana kita telah ditolak 25 daripada nilai awal kami 41. Dan kita mempunyai 16 kiri untuk sen kami. Adakah semua orang memahami bagaimana program ini melangkah dan mengapa sen kini telah menjadi 16 dan mengapa, sekarang, syiling telah menjadi 1? Adakah semua orang mengikut logik itu? Sejuk. Jadi pada ketika ini, kerja program ini, bukan? Kita tahu ia lakukan betul-betul apa yang kita mahu ia. Dan kita tidak benar-benar perlu mencetak, oh, apa adalah sen pada masa ini, apa yang syiling pada ketika ini. Kami terus melalui program ini. Melangkah. Sejuk. Kami akan ke dimes. Yang besar. Kita lihat bahawa ia diambil kira $ 0,10 untuk ada yang. Dan sekarang kita mempunyai dua syiling. Itulah betul. Kami pergi ke atas beberapa sen dan kita lihat bahawa kami telah mendapat ditinggalkan sen. Hmm, itu pelik. Di sini pada program itu, saya sepatutnya telah ditolak beberapa sen saya. Mungkin saya hanya tidak melakukan hak itu garis. Dan malangnya, anda boleh melihat di sini, kerana kita tahu bahawa kita melangkah melalui talian 32 dan 33, itulah di mana program kami secara tidak wajar mempunyai pembolehubah berjalan. Oleh itu, kita boleh melihat dan melihat, oh, Saya menolak sen sini, tetapi saya tidak benar-benar menambah nilai duit syiling saya. Saya menambah untuk sen. Dan saya tidak mahu menambah sen, saya ingin menambah duit syiling. Jadi, jika kita menukar bahawa untuk syiling, kami mempunyai program kerja. Saya boleh menjalankan check50. Anda hanya boleh keluar daripada GDB betul di sini dan kemudian berjalan check50 lagi. Saya hanya boleh melakukan ini. Saya perlu membuat tamak. 0.41. Dan di sini, ia percetakan jawapan yang betul. Jadi seperti yang anda semua boleh lihat, GDB adalah alat yang benar-benar kuat apabila kita mempunyai begitu banyak kod berlaku dan begitu banyak pembolehubah bahawa ia sukar untuk kita, kerana manusia, untuk mengesan. Komputer, dalam GDB penyahpepijat, mempunyai keupayaan untuk mengesan segala-galanya. Saya tahu, dalam Visionaire, anda semua mungkin mungkin telah melanda beberapa kesalahan segmentasi kerana anda sedang berlari di luar batas array anda. Dalam contoh Caesar, itu apa yang saya telah dilaksanakan di sini. Jadi saya terlupa untuk memeriksa apa yang akan berlaku jika saya tidak mempunyai dua hujah baris arahan. Saya hanya tidak dimasukkan ke dalam daftar itu. Dan jadi jika saya menjalankan Debug-- saya menetapkan titik putus saya ke kanan sana. Saya menjalankan Debug. OKAY. Yeah. Jadi sebenarnya, GDB sepatutnya telah memberitahu saya ada adalah satu kesalahan segmentasi sana. Saya tidak tahu apa yang berlaku di sana, tetapi apabila saya berlari, ia telah bekerja. Apabila anda menjalankan baris kod melalui dan GDB mungkin hanya tiba-tiba berhenti pada anda, naik dan lihat apa kesilapan merah. Ia akan memberitahu anda, hey, anda mempunyai kesalahan segmentasi, yang bermaksud bahawa anda cuba untuk akses ruang dalam array yang tidak wujud. Yeah. Jadi, dalam masalah yang akan datang menetapkan minggu ini, anda semua mungkin akan mempunyai banyak pembolehubah terapung di sekeliling. Anda tidak akan menjadi pasti apa membawa makna pada titik tertentu. Jadi GDB benar-benar akan membantu anda dalam memikirkan mengetahui apa yang mereka semua menyamai dan dapat melihat bahawa secara visual. Adakah sesiapa yang keliru tentang bagaimana mana-mana yang bekerja? Sejuk. Baiklah. Jadi, selepas itu, kami akan digalakkan untuk ke empat yang berbeza jenis jenis untuk minggu ini. Berapa ramai daripada anda, pertama sekali, sebelum kita bermula, telah membaca keseluruhan spec untuk pset3? OKAY. Saya bangga dengan anda semua. Itu seperti separuh daripada kelas, yang adalah lebih banyak daripada masa lalu. Jadi yang hebat, kerana apabila kita bercakap mengenai kandungan dalam lecture-- atau maaf, dalam seksyen ini- saya suka untuk mengaitkan banyak yang kembali kepada apa yang pset adalah dan bagaimana anda mahu melaksanakan bahawa dalam pset anda. Jadi, jika anda datang mempunyai membaca spec, ia akan mempunyai menjadi lebih mudah bagi anda untuk memahami apa yang saya bercakap tentang apabila saya berkata, oh hey, ini mungkin benar-benar Tempat yang baik untuk melaksanakan seperti ini. Maka orang-orang di antara kamu yang telah membaca spec tahu bahawa, sebagai sebahagian daripada pset anda, anda akan perlu menulis sejenis macam. Jadi ini mungkin sangat berguna untuk banyak anda hari ini. Oleh itu, kita akan mulakan dengan, pada dasarnya, jenis yang paling mudah daripada jenis, jenis pemilihan. Algoritma khas untuk bagaimana kita akan pergi tentang perkara ini is-- David telah melalui ini semua dalam kuliah, jadi saya dengan cepat akan bergerak bersama-sama sini-- asasnya, anda mempunyai pelbagai nilai. Dan kemudian anda mencari nilai terisih kecil dan anda menukar nilai itu dengan nilai terisih pertama. Dan kemudian anda hanya terus mengulangi dengan seluruh senarai anda. Dan di sini adalah penerangan visual bagaimana yang akan bekerja. Jadi, sebagai contoh, jika kita mula dengan pelbagai lima elemen, indeks 0-4, dengan 3, 5, 2, 6, dan 4 nilai diletakkan di array-- sehingga sekarang, kami hanya akan menganggap bahawa mereka semua terisih kerana kita tidak diuji sebaliknya. Jadi bagaimana jenis pemilihan akan kerja adalah bahawa ia akan pertama berjalan melalui keseluruhannya yang array terisih. Ia akan memilih nilai yang paling kecil. Dalam kes ini, 3, betul-betul sekarang, adalah yang paling kecil. Ia mendapat hingga 5. Nope, 5 tidak lebih besar than-- atau maaf, tidak kurang than-- 3. Jadi nilai minimum masih 3. Dan kemudian anda boleh 2. Komputer melihat, oh, 2 adalah kurang daripada 3. 2 kini perlu menjadi nilai minimum. Dan sebagainya 2 swap dengan bahawa nilai pertama. Jadi selepas satu pas, kita memang melihat bahawa 2 dan 3 adalah bertukar. Dan kita hanya akan terus melakukan ini sekali lagi dengan seluruh array. Oleh itu, kita akan berjalan melalui lepas empat indeks array. Kita akan melihat bahawa 3 adalah nilai minimum yang akan datang. Jadi, kita akan menukar bahawa dengan 4. Dan kemudian kita hanya akan menyimpan berjalan melalui, sehingga akhirnya, anda mendapatkan kepada pelbagai disusun di mana 2, 3, 4, 5, dan 6 semuanya disusun. Adakah semua orang memahami logik yang bagaimana sebuah jenis pemilihan berfungsi? Anda hanya mempunyai beberapa jenis daripada nilai minimum. Anda mengesan apa yang. Dan setiap kali anda mencari, anda tukar dengan nilai pertama dalam array-- yang atau, tidak value-- pertama nilai seterusnya dalam array. Sejuk. Jadi seperti yang anda semua jenis melihat dari gambaran ringkas, kita akan pseudokod ini keluar. Jadi, jika anda seorang lelaki di belakang mahu membentuk satu kumpulan, semua orang di meja boleh membentuk rakan kongsi sedikit, saya akan untuk memberikan anda semua suka tiga minit hanya bercakap melalui logik, dalam bahasa Inggeris, bagaimana kita mungkin dapat melaksanakan pseudokod untuk menulis satu bentuk pemilihan. Dan ada gula-gula. Sila datang dan mendapatkan gula-gula. Jika anda berada di belakang dan anda mahu gula-gula, saya boleh membuang gula-gula pada anda. Sebenarnya, tidak sejuk atasmu. Oh maaf. OKAY. Jadi, jika kita mahu, sebagai kelas, menulis kod pseudo untuk bagaimana seseorang boleh meminta masalah ini, hanya berasa bebas. Saya hanya akan pergi sekitar dan, teratur, meminta kumpulan untuk baris seterusnya apa yang kita harus lakukan. Jadi jika anda semua ingin memulakan off, apa perkara pertama yang perlu dilakukan apabila anda cuba untuk melaksanakan satu cara untuk menyelesaikan program ini untuk terpilih menyusun senarai? Mari kita menganggap kita mempunyai pelbagai, boleh? PENONTON: Anda ingin membuat beberapa semacam [didengar] bahawa anda berjalan melalui seluruh lokasi anda. ANDI PENG: Betul. Jadi, anda akan mahu untuk melelar melalui setiap ruang, bukan? Jadi, yang besar. Jika anda lelaki mahu memberi saya berikut garis ini-- yeah, di belakang. PENONTON: Periksa mereka semua untuk yang paling kecil. ANDI PENG: Ada kita pergi. Oleh itu, kita mahu pergi melalui dan semak untuk melihat apa nilai minimum adalah, bukan? Saya akan menyingkatkan ke "min." Apa yang anda semua mahu lakukan selepas anda memperolehi nilai minimum? PENONTON: [didengar] ANDI PENG: Jadi, anda akan mahu untuk hidupkan ia dengan yang pertama array itu, bukan? Itulah permulaan, saya akan katakan. Baiklah. Jadi sekarang bahawa anda telah bertukar pertama salah, apa yang anda mahu lakukan selepas itu? Jadi sekarang kita tahu bahawa salah satu ini di sini mesti menjadi nilai yang paling kecil, bukan? Maka anda mempunyai rehat tambahan array itulah terisih. Jadi apa yang anda mahu lakukan di sini, jika anda lelaki mahu memberi saya baris seterusnya? PENONTON: Oleh itu, maka anda mahu untuk melelar melalui baki array. ANDI PENG: Ya. Dan sebagainya apakah iterating melalui jenis membayangkan kita mungkin akan perlukan? Apakah jenis daripada- PENONTON: Oh, pembolehubah tambahan? ANDI PENG: Mungkin lain untuk gelung, bukan? Oleh itu, kita mungkin akan mahu untuk melelar through-- besar. Dan kemudian anda akan kembali dan mungkin menyemak minimum sekali lagi, bukan? Dan anda akan terus mengulangi ini, kerana gelung hanya akan untuk terus berjalan, bukan? Jadi seperti yang anda semua boleh lihat, kami hanya mempunyai kod pseudo umum bagaimana kita mahu program ini untuk melihat. Itekadar ini di sini, apa yang kita biasanya perlu menulis kod kami jika kita mahu untuk melelar melalui pelbagai, apa jenis struktur? Saya rasa Christabel telah berkata ini sebelum ini. PENONTON: A untuk gelung. ANDI PENG: A untuk gelung? Tepat sekali. Jadi ini mungkin akan menjadi satu untuk gelung. Apa yang cek di sini akan membayangkan? Biasanya, jika anda mahu untuk memeriksa jika sesuatu adalah sesuatu else-- PENONTON: Jika. ANDI PENG: Seorang jika, bukan? Dan kemudian swap di sini, kita akan pergi lebih kemudian, kerana Daud pergi melalui itu dalam kuliah juga. Dan kemudian Itekadar kedua implies-- PENONTON: Satu lagi untuk gelung. ANDI PENG: --another untuk gelung, betul-betul. Jadi, jika kita sedang pada ini dengan betul, kita dapat melihat bahawa kami mungkin akan memerlukan bersarang untuk gelung dengan suatu pernyataan bersyarat di sana dan kemudian sekeping sebenar kod yang yang akan menukar nilai-nilai. Jadi saya hanya umumnya bertulis kod kod pseudo di sini. Dan kemudian kita sebenarnya akan secara fizikal, sebagai sebuah kelas, cuba untuk melaksanakan hari ini. Mari kita kembali ke dalam IDE ini. Uh-oh. Mengapa yang tidak-- ada ia. OKAY. Maaf, saya cuba untuk zum dalam sedikit lebih. Di sana kami pergi. Semua yang saya lakukan di sini saya telah membuat program yang dikenali sebagai "pemilihan / sort.c." Saya telah membuat pelbagai sembilan nilai, 4, 8, 2, 1, 6, 9, 7, 5, 3. Pada masa ini, yang anda boleh melihat, mereka tidak tertib. n akan menjadi bilangan yang memberitahu anda jumlah nilai anda ada dalam pelbagai anda. Dalam kes ini, kita ada sembilan nilai. Dan saya baru sahaja mendapat untuk gelung di sini yang mencetak keluar array terisih. Dan pada akhirnya, saya juga telah mendapat untuk gelung yang hanya mencetak ia keluar lagi. Jadi secara teori, jika program ini berfungsi dengan betul, pada akhirnya, anda akan dapat melihat dicetak untuk gelung di mana 1, 2, 3, 4, 5, 6, 7, 8, 9 semua dengan betul. Jadi kita telah mendapat pseudokod kami di sini. Adakah sesiapa yang mahu supaya- saya hanya akan pergi meminta volunteers-- beritahu saya apa yang perlu menaip jika kita mahu, pertama, hanya melelar melalui permulaan array ini? Apa yang baris kod Saya mungkin akan perlukan di sini? PENONTON: [didengar] ANDI PENG: Ya, sila percuma supaya- maaf, anda tidak perlu berdiri rasa up-- percuma untuk menujukan suaramu sedikit. PENONTON: Untuk int i sama 0-- ANDI PENG: Ya, baik. PENONTON: i adalah kurang daripada panjang array. ANDI PENG: Jadi perlu kisah di sini, kerana kita tidak mempunyai fungsi yang memberitahu kita panjang array, kita sudah mempunyai nilai yang menyimpan itu. Betul? Satu lagi perkara yang perlu dalam mind-- dalam array sembilan nilai, apakah indeks? Mari kita katakan pelbagai ini adalah 0-3. Anda melihat bahawa yang terakhir indeks sebenarnya 3. Ia bukan 4, walaupun ada empat nilai dalam tatasusunan. Jadi di sini, kita perlu berhati-hati apa keadaan kita untuk panjang akan menjadi. PENONTON: Bukankah lebih n tolak 1? ANDI PENG: Ia akan n tolak 1, betul-betul. Adakah ini masuk akal, mengapa ia n tolak 1, semua orang? Ini kerana tatasusunan adalah sifar-diindeks. Mereka bermula pada 0 dan melarikan diri hingga ke n tolak 1. Ya, ia agak rumit. OKAY. Dan then-- PENONTON: Isnt'1 yang sudah dijaga walaupun, dengan hanya tidak mengatakan "kurang daripada atau sama dengan "dan hanya mengatakan" kurang daripada " ANDI PENG: Itu satu soalan yang benar-benar baik. Jadi, ya. Tetapi juga, cara yang kita berada melaksanakan hak memeriksa, anda perlu membandingkan dua nilai. Jadi, anda benar-benar ingin meninggalkan "kepada" kosong. Kerana jika anda membandingkan satu ini, anda tidak akan mempunyai apa-apa selepas ia untuk membandingkan, bukan? Yeah. Jadi saya ++. Mari kita menambah kurungan kami di. Alamak. Yang besar. Jadi kita mempunyai permulaan gelung luar kami. Jadi sekarang kita mungkin mahu mewujudkan pemboleh ubah untuk menjaga mengesan nilai yang paling kecil, bukan? Adakah sesiapa yang mahu memberi saya baris kod yang akan berbuat demikian? Apa yang kita perlukan jika kita akan mahu menyimpan sesuatu? Betul. Mungkin nama yang lebih baik untuk akan adalah- "temp" benar-benar works-- mungkin yang lebih tepat dinamakan akan menjadi, jika kita mahu value-- yang paling kecil PENONTON: Min. ANDI PENG: min, ada kita pergi. min akan menjadi baik. Dan sebagainya di sini, apa yang kita mahu untuk memulakan ke? Ini adalah agak sukar. Kerana sekarang di permulaan pelbagai ini, anda belum melihat apa-apa, kan? Jadi apa, secara automatik, jika kita berada pada i sama dengan 0, apa yang kita mahu untuk memulakan nilai minimum pertama kami ke? PENONTON: i. ANDI PENG: i, betul-betul. Christabel, mengapa kita mahu untuk memulakan kepada i? PENONTON: Kerana, baik, kita bermula dengan 0. Jadi kerana kita mempunyai apa-apa untuk membandingkan kepada, sekurang-kurangnya akan berakhir menjadi 0. ANDI PENG: Tepat sekali. Jadi dia betul-betul betul. Oleh kerana kita tidak benar-benar melihat apa-apa lagi, kita tidak tahu apa nilai minimum kita. Kami mahu hanya memulakan ia ke i, yang, pada masa ini, adalah di sini. Dan seperti yang kita terus bergerak ke bawah pelbagai ini, kita akan melihat bahawa, dengan setiap pas tambahan, i kenaikan. Dan sebagainya pada ketika itu, i mungkin akan mahu menjadi minimum, kerana ia akan menjadi apa sahaja adalah permulaan array terisih. Sejuk. Jadi sekarang kita mahu menambah untuk gelung di sini bahawa akan melelar melalui terisih, atau seluruh pelbagai ini. Adakah sesiapa yang mahu memberikan saya baris kod yang akan berbuat demikian? Hint-- apa yang kita perlu turun di sini? Apa yang akan pergi dalam ini untuk gelung? Yeah. PENONTON: Oleh itu, kita akan mahu mempunyai integer yang berbeza, kerana kita berjalan melalui yang lain array bukannya i, jadi mungkin j. ANDI PENG: Ya, j bunyi yang baik kepada saya. Sama? PENONTON: Jadi akan i campur 1, kerana anda bermula pada nilai yang seterusnya. Dan kemudian untuk end-- apa lagi, j adalah kurang daripada n tolak 1, dan kemudian j ++. ANDI PENG: Great. Dan kemudian di sini, kami akan mahu untuk memeriksa untuk melihat jika keadaan kita dipenuhi, bukan? Kerana anda mahu menukar nilai minimum jika ia sebenarnya lebih kecil daripada apa yang anda membandingkannya dengan, bukan? Jadi apa yang kita akan mahu di sini? Semak untuk melihat. Apa jenis penyataan kita mungkin akan ti mahu menggunakan jika kita mahu untuk memeriksa sesuatu? PENONTON: An jika kenyataan. ANDI PENG: Seorang jika kenyataan. Jadi jika- dan apa yang akan menjadi syarat kita mahu di dalam daripada jika kenyataan kami? PENONTON: Jika nilai j adalah kurang daripada nilai Saya-- ANDI PENG: Tepat sekali. Jadi jika- supaya pelbagai ini dipanggil "pelbagai." Yang besar. Jadi, jika array-- apa tu? Cakap sekali lagi. PENONTON: Jika lokasi benar-j adalah kurang daripada lokasi benar-i, maka kita akan mengubah min. Jadi min itu akan menjadi j. ANDI PENG: Adakah ini masuk akal? OKAY. Dan kini turun di sini, kita benar-benar mahu melaksanakan swap, bukan? Jadi ingat, dalam kuliah, yang Daud, ketika dia cuba untuk menukar the-- apa yang jus oren kitab itu dan milk-- PENONTON: Itu adalah kasar. ANDI PENG: Ya, itu adalah jenis kasar. Tetapi ia adalah baik cukup konsep menunjukkan masa. Jadi berfikir nilai-nilai anda di sini. Anda telah mendapat array min, pelbagai i, atau apa sahaja yang kita sedang berusaha untuk menukar sini. Dan anda mungkin tidak boleh menuangkannya ke dalam antara satu sama lain pada masa yang sama, bukan? Jadi apa yang kita akan untuk perlu membuat di sini untuk menukar nilai-nilai yang betul? PENONTON: Pemboleh ubah sementara. ANDI PENG: Pemboleh ubah sementara. Jadi mari kita buat int temp. Lihat, ini akan menjadi yang lebih baik masa supaya- wah, apa tu? OKAY. Jadi ini akan menjadi yang lebih baik masa untuk menamakan "temp." berubah-ubah Jadi mari kita buat int temp. Apa yang kita akan menetapkan temp sama ke sini? PENONTON: Min? ANDI PENG: Ia agak rumit. Ia sebenarnya tidak penting pada akhirnya. Tidak kira apa perintah yang anda pilih untuk menukar dalam selagi anda membuat pasti anda berada mengesan apa yang anda bertukar-tukar. PENONTON: Ia boleh menjadi lokasi benar-i. ANDI PENG: Ya, mari kita buat pelbagai-i. Dan kemudian apa yang baris seterusnya kod kita mahu ada di sini? PENONTON: lokasi benar-i sama pelbagai-j. ANDI PENG: Dan akhir sekali? PENONTON: lokasi benar-j sama dengan lokasi-i. PENONTON: Atau lokasi benar-j setaraf lokasi benar-temp-- atau, temp. ANDI PENG: OK. Jadi mari kita berjalan ini dan melihat jika ia akan bekerja. Di mana yang berlaku? Oh, itu masalah. Lihat, di laluan 40, kami cuba menggunakan pelbagai-j? Tetapi di mana j hanya wujud di dalam? PENONTON: Pada untuk gelung. ANDI PENG: Betul. Jadi apa yang kita akan perlu lakukan? PENONTON: Tentukan di luar the-- PENONTON: Ya, saya rasa anda perlu untuk menggunakan satu lagi jika kenyataan, bukan? Jadi seperti, jika minimum-- yang baiklah, saya fikir. ANDI PENG: Guys, cuba untuk mengambil lihat Mari lihat, apa yang sesuatu yang kita boleh lakukan di sini? PENONTON: OK. Jadi, jika minimum yang tidak sama j-- jadi jika minimum masih Saya-- maka kita tidak akan mempunyai untuk menukar. ANDI PENG: Adakah yang sama i? Apa yang anda ingin katakan di sini? PENONTON: Atau yeah, jika minimum tidak sama i, yeah. ANDI PENG: OK. Baik yang menyelesaikan, jenis, masalah kita. Tetapi itu masih tidak menyelesaikan masalah apa yang berlaku jika j-- sejak j tidak wujud di luar daripadanya dan apa adakah anda yang kami mahu lakukan dengannya? Mengisytiharkan ia di luar? Mari kita cuba berjalan ini. Uh-oh. Semacam kita tidak berfungsi. Seperti yang anda lihat, awal kami lokasi benar mempunyai nilai-nilai. Dan selepas itu ia perlu mempunyai berada dalam 1, 2, 3, 4, 5, 6, 7, 8, 9. Ia tidak berfungsi. Ahh. Apa yang kita lakukan? PENONTON: Debug. ANDI PENG: Baiklah, kita boleh cuba itu. Kami boleh debug. Zum keluar sedikit. Mari kita menetapkan titik putus kami. Mari kita pergi OK like--. Demikian kerana kita sudah tahu bahawa ayat-ayat ini, 15 hingga 22, sedang working-- kerana semua yang saya lakukan adalah hanya iterating melalui dan printing-- Saya boleh pergi ke hadapan dan skip itu. Mari kita mulakan di talian 25. Oop, biarlah saya menghilangkan itu. PENONTON: Jadi titik putus ini mana debugging bermula? ANDI PENG: Atau berhenti. PENONTON: Atau berhenti. ANDI PENG: Ya. Anda boleh menetapkan beberapa titik putus dan ia hanya boleh melompat dari satu kepada yang lain. Tetapi dalam kes ini kita tidak tahu di mana kesilapan yang berlaku. Oleh itu, kita hanya mahu bermula dari atas ke bawah. Ya. OKAY. Jadi garis ini di sini, kita boleh campur tangan. Anda boleh lihat di bawah ini, kami mempunyai array. Mereka adalah nilai-nilai yang berada di dalam array. Adakah anda melihat bahawa, bagaimana indeks 0, ia sepadan dengan value-- oh, Saya akan cuba untuk zum masuk. Maaf, ia benar-benar keras untuk see-- di pelbagai indeks 0, kita mempunyai nilai 4 dan kemudian sebagainya dan sebagainya. Kami mempunyai pembolehubah tempatan. Sekarang i adalah sama dengan 0, yang kita mahu ia menjadi. Dan begitu mari kita melangkah. Minimum kami adalah sama dengan 0, yang kita juga mahu ia menjadi. Dan kemudian kita masukkan kedua kami untuk gelung, jika lokasi benar-j kurang daripada lokasi benar-i, yang ia tidak. Jadi adakah anda melihat bagaimana yang dilangkau lebih itu? PENONTON: Jadi sekiranya jika minimum, semua bahawa- tidak sepatutnya yang berada di dalam yang pertama untuk gelung? ANDI PENG: Tidak, kerana anda masih mahu menguji. Anda mahu melakukan perbandingan setiap masa, walaupun selepas anda menjalankan melaluinya. Anda tidak hanya mahu melakukannya pada pertama lulus-melalui. Anda mahu melakukannya dengan setiap laluan tambahan lagi. Jadi, anda mahu untuk memeriksa keadaan anda di dalam. Oleh itu, kita hanya akan terus berjalan melalui sini. Saya akan memberikan anda semua petunjuk. Ia mempunyai kaitan dengan hakikat bahawa apabila anda memeriksa bersyarat anda, anda tidak mendaftar indeks yang betul. Jadi sekarang anda memeriksa indeks pelbagai j kurang daripada lokasi indeks i. Tetapi apa yang anda lakukan ke arah permulaan untuk gelung? Adakah anda tidak menetapkan j sama dengan i? Ya, jadi kita boleh sebenarnya keluar penyahpepijat sini. Oleh itu, mari kita lihat pada kod pseudo kami. Bagi- kita akan bermula dari i sama dengan 0. Kami akan pergi sehingga n tolak 1. Mari kita lihat, adakah kita mempunyai hak itu? Ya, itu adalah betul. Sebab itu di dalam sini, kami akan mewujudkan nilai minimum dan menetapkan yang sama dengan i. Adakah kita berbuat demikian? Ya, melakukannya. Sekarang di dalam untuk gelung kami, kami akan melakukan j sama i n tolak 1. Adakah kita berbuat demikian? Sesungguhnya, kita lakukan itu. Jadi bagaimanapun, apa yang kita membandingkan di sini? PENONTON: j plus 1. ANDI PENG: Tepat sekali. Dan kemudian anda akan mahu untuk menetapkan minimum anda sama dengan j plus 1 juga. Jadi saya pergi melalui itu benar-benar cepat. Adakah anda semua faham mengapa ia j plus 1? OKAY. Jadi dalam lokasi anda, dalam pas pertama anda melalui, anda untuk gelung, untuk int i sama dengan 0, mari kita menganggap ini tidak berubah lagi. Kami mempunyai pelbagai, benar-benar, hanya empat unsur terisih, bukan? Oleh itu, kita mahu untuk memulakan i sama dengan 0. Dan saya akan hanya berjalan melalui gelung ini. Dan sebagainya dalam laluan pertama, kita akan untuk memulakan pembolehubah yang dipanggil "min" yang juga sama dengan i, kerana kita tidak mempunyai nilai minimum. Jadi itu kini sama dengan 0 juga. Dan kemudian kita akan melalui. Dan kita mahu untuk melelar lagi. Sekarang kita telah dapati apa yang minimum kami adalah, kita mahu untuk melelar melalui sekali lagi untuk melihat jika ia membandingkan, bukan? Jadi j, di sini, akan untuk sama i, yang adalah 0. Dan kemudian jika pelbagai j plus i, yang adalah satu yang akan datang ke atas, sebagai kurang daripada apa yang minimum semasa anda nilai adalah, anda mahu untuk menukar. Jadi mari kita hanya mengatakan kami telah mendapat, seperti, 2, 5, 1, 8. Buat masa ini, i adalah sama dengan 0 dan j adalah sama dengan 0. Dan itulah nilai minimum kami. Jika lokasi benar-j plus Saya-- supaya jika yang itulah selepas yang kita sedang melihat adalah lebih besar daripada yang di hadapannya, ia akan menjadi minimum. Jadi di sini kita melihat bahawa 5 tidak kurang daripada itu. Jadi ia akan tidak 5. Kita lihat bahawa 1 adalah kurang daripada 2, bukan? Jadi sekarang kita tahu bahawa kita adalah minimum akan menjadi nilai indeks pada 0, 1, 2. Ya? Dan kemudian apabila anda turun di sini, anda boleh menukar nilai yang betul. Oleh itu, apabila kamu telah hanya mempunyai j sebelum ini, anda tidak melihat apa-apa yang selepas itu. Anda telah melihat nilai sama, yang sebabnya ia hanya tidak melakukan apa-apa. Adakah ini masuk akal untuk semua orang, mengapa kita memerlukan bahawa campur 1 di sana? OKAY. Sekarang mari kita berjalan melalui untuk membuat memastikan seluruh kod adalah betul. Mengapa yang berlaku? Ah, ia adalah min di sini. Kami membandingkan nilai yang salah. Oh tidak. Oh yeah, turun di sini kita bertukar-tukar nilai yang salah juga. Oleh kerana kita telah melihat i dan j. Mereka adalah orang-orang kita telah memeriksa. Kami benar-benar mahu menukar minimum, minimum semasa, dengan apa sahaja yang seseorang di luar itu. Dan seperti yang anda semua boleh melihat ke bawah di sini, kami mempunyai pelbagai disusun. Ia hanya mempunyai kaitan dengan hakikat bahawa apabila kita telah memeriksa nilai yang kita telah membandingkan, kami tidak melihat nilai-nilai yang betul. Kita telah melihat satu yang sama di sini, tidak sebenarnya bertukar-tukar ia. Anda perlu melihat yang seterusnya kepadanya dan kemudian anda boleh menukar. Jadi itulah yang adalah jenis bugging kod kami sebelum ini. Dan apa yang saya lakukan di sini adalah segala-galanya penyahpepijat boleh dilakukan untuk anda Saya hanya melakukannya pada kapal, kerana lebih mudah untuk melihat dan bukannya cuba untuk mengezum masuk pada penyahpepijat. Adakah ini masuk akal untuk semua orang? Sejuk. Baiklah. Kami boleh bergerak untuk bercakap tentang notasi asimptot, yang hanya cara mewah untuk mengatakan yang runtimes semua macam ini. Jadi saya tahu Daud, dalam kuliah, menyentuh runtimes. Dan dia pergi melalui seluruh formula bagaimana untuk mengira runtimes. Tidak perlu risau tentang itu. Jika anda benar-benar ingin tahu bagaimana yang bekerja, berasa bebas untuk bercakap dengan saya selepas seksyen. Kita boleh berjalan melalui formula bersama-sama. Tetapi semua anda semua mempunyai untuk benar-benar tahu ialah n kuasa lebih 2 adalah perkara yang sama seperti n kuasa dua. Oleh kerana bilangan yang terbesar, eksponen, tumbuh yang paling. Dan sebagainya untuk tujuan kita, semua kita mengambil berat tentang ialah bilangan gergasi yang semakin berkembang. Jadi apa kes yang terbaik runtime daripada jenis pemilihan? Jika anda akan mempunyai untuk melelar melalui senarai dan kemudian melelar melalui yang lain dalam senarai itu, berapa kali yang anda akan mungkin, dalam case-- yang paling teruk dalam kes terbaik, sorry-- berjalan melalui? Mungkin soalan yang lebih baik adalah bertanya, apakah kes yang paling teruk runtime seumpama pemilihan. PENONTON: n kuasa dua. ANDI PENG: Ia n kuasa, betul. Jadi cara yang mudah untuk berfikir ini adalah seperti, bila-bila masa anda mempunyai dua bersarang untuk gelung, ia akan dapat n kuasa dua. Kerana bukan sahaja anda berjalan melalui sekali lagi, anda perlu kembali dan berlari melaluinya sekali lagi dalam untuk setiap nilai. Jadi, dalam kes itu, anda menjalankan n kali n kuasa, yang is-- maaf, n kali n, yang bersamaan n kuasa dua. Dan jenis juga sedikit unik dalam erti kata bahawa ia tidak kira jika ini nilai-nilai yang sudah teratur. Ia masih akan berjalan melalui anyways. Mari kita katakan ini adalah 1, 2, 3, 4. Tidak kira sama ada atau tidak ia adalah pada perintah, ia masih akan berlari melalui dan masih diperiksa nilai minimum. Ia akan menjadikan Bilangan yang sama cek setiap kali, walaupun ia sebenarnya tidak menyentuh apa-apa. Jadi, dalam kes seperti itu, yang terbaik dan paling teruk runtimes sebenarnya setara. Jadi runtime yang dijangka daripada jenis pemilihan, mana kita menetapkan dengan simbol theta, theta, dalam kes ini, juga akan n kuasa dua. Ketiga-tiga akan n kuasa dua. Adakah semua orang jelas mengapa masa pengeluaran adalah n kuasa? Baiklah. Jadi, saya hanya akan cepat berjalan melalui seluruh macam. Algoritma bagi gelembung sort-- ingat, ini adalah yang pertama Daud pergi ke sana dalam kuliah. Pada asasnya, anda langkah melalui seluruh senarai dan anda swap-- anda hanya membandingkan dua pada satu masa. Dan jika seseorang yang lebih besar, daripada anda hanya menukar mereka. Jadi, jika ini adalah lebih besar, anda akan menukar. Saya ada rasmi di sini. Jadi mari kita hanya mengatakan anda mempunyai 8, 6, 4, 2. Anda akan membandingkan 8 dan 6. Anda akan perlu untuk menukar mereka. Anda akan membandingkan 8 dan 4. Anda akan perlu untuk menukar mereka. Jika anda perlu menukar 8 dan 2, menukar mereka juga. Jadi dalam apa-apa segi, yang anda lihat, dimainkan dalam tempoh masa yang panjang, bagaimana jenis nilai-nilai yang gelembung untuk hujung, yang adalah mengapa kita panggil semacam gelembung. Kami hanya akan berjalan melalui sekali lagi pada pas kedua kami, dan pas ketiga kami, dan pas keempat kami. Pada dasarnya, gelembung semacam hanya berjalan sehingga anda tidak membuat apa-apa lagi swap. Jadi dalam erti kata itu, ini adalah hanya yang pseudokod umum untuk itu. Jangan bimbang, ini semua akan berada dalam talian. Kami tidak mempunyai untuk benar-benar pergi ke ini. Kami hanya memulakan kaunter pembolehubah yang bermula pada 0. Dan kita melelar melalui pelbagai keseluruhan. Dan jika satu nilai is-- jika ini nilai adalah lebih besar daripada nilai itu, anda akan menukar mereka. Dan kemudian anda hanya akan terus pergi. Dan anda akan dapat dihitung. Dan anda hanya akan terus melakukan ini manakala kaunter adalah lebih besar daripada 0, yang bermaksud bahawa setiap kali anda mempunyai untuk menukar, anda tahu anda mahu pergi belakang dan semak sekali lagi. Anda mahu menyimpan semakan sehingga anda tahu bahawa anda tidak perlu untuk menukar lagi. Jadi apa yang adalah yang terbaik dan paling teruk kes runtimes untuk jenis gelembung? Dan hint-- ini sebenarnya berbeza dari jenis pemilihan dalam erti kata bahawa kedua-dua jawapan tidak sama. Fikirkan tentang apa yang akan berlaku dalam kes jika ia sudah disusun. Dan berfikir tentang apa yang akan berlaku jika ia dalam kes di mana ia tidak disusun. Dan anda jenis boleh menjalankan melalui mengapa yang berlaku. Saya akan memberikan anda semua, seperti, 30 saat untuk berfikir tentang itu. OKAY. Adakah sesiapa yang mempunyai meneka apa yang kes terburuk runtime semacam gelembung? Yeah. PENONTON: ia akan menjadi, seperti, n kali n tolak 1 atau sesuatu seperti itu? Seperti, setiap kali ia berjalan, ia hanya, seperti, satu swap kurang bahawa apa sahaja yang ia adalah. ANDI PENG: Ya, jadi anda benar-benar betul. Dan ini adalah satu kes di mana anda jawapan sebenarnya lebih kompleks daripada apa yang kita perlu memberi. Jadi ia akan run-- Saya akan memadamkan semua ini di sini. Adakah semua orang yang baik? Bolehkah saya memadam ini? OKAY. Anda akan berjalan melalui n kali kali pertama, bukan? Dan mereka akan berjalan melalui n tolak 1 kali kedua, bukan? Dan kemudian anda akan menyimpan pergi, n saya 2, dan sebagainya. David melakukan ini di dalam satu ceramah, di mana, jika anda tambah semua nilai-nilai, anda mendapat sesuatu yang like-- yeah-- lebih 2, yang pada dasarnya hanya mengurangkan turun ke n kuasa dua. Anda akan mendapat pecahan pelik di sana. Dan sebagainya hanya tahu bahawa n kuasa dua sentiasa diberi keutamaan berbanding pecahan tersebut. Dan jadi dalam kes ini, yang paling teruk runtime akan n kuasa dua. Jika ia ada turun perintah, berfikir, anda perlu membuat pertukaran setiap kali. Apa yang akan menjadi, berpotensi, mana yang terbaik runtime? Mari kita katakan, jika senarai itu sudah teratur, apa yang akan runtime menjadi? PENONTON: n. ANDI PENG: Ia n, betul-betul. Dan mengapa ia n? PENONTON: Kerana anda hanya perlu menyemak pada setiap sekali. ANDI PENG: Tepat sekali. Jadi, dalam masa jalan yang terbaik, jika senarai ini sudah sorted-- katakan 1, 2, 3, 4-- anda hanya akan melalui, anda akan memeriksa, anda akan melihat, oh, mereka semua berjalan baik. Saya tidak mempunyai untuk menukar. Aku selesai. Jadi, dalam kes itu, ia hanya n atau bilangan langkah anda hanya terpaksa memeriksa dalam senarai pertama. Dan selepas itu, kita kini melanda jenis kemasukan, di mana algoritma pada dasarnya untuk jurang ke dalam bahagian yang disusun dan terisih. Dan kemudian satu demi satu, nilai-nilai yang terisih dimasukkan ke dalam yang sesuai mereka jawatan di awal senarai. Jadi, sebagai contoh, kita mempunyai senarai 3, 5, 2, 6, 4 lagi. Kita tahu bahawa ia kini Unsorted kerana kita baru sahaja mula melihat ia. Kita lihat dan kita tahu bahawa nilai pertama disusun, bukan? Jika anda hanya melihat pelbagai saiz satu, anda tahu bahawa ia disusun. Sebab itu kita tahu bahawa empat yang terisih. Kita melalui dan kita melihat nilai itu. Mari kita kembali. Melihat bahawa nilai 5? Kami mengambil melihat pada ia. Kami membandingkannya dengan 3. Kita tahu bahawa itu lebih besar daripada 3, jadi kita tahu bahawa yang yang disusun. Oleh itu, kita kini tahu bahawa kedua-dua pertama disusun dan tiga lepas tidak. Kita lihat pada 2. Kami periksa dengan 5. Adakah kurang daripada 5? Bukan. Oleh itu, kita perlu terus melihat ke bawah. Kemudian anda menyemak 2 luar 3. Adakah kurang daripada? No. Jadi, anda tahu yang 2 perlu dimasukkan ke hadapan dan 3 dan 5 kedua-duanya mempunyai peluang untuk diketengahkan. Adakah ini sekali lagi dengan 6 dan 4. Dan kita hanya terus mendaftar pada dasarnya, di mana kita hanya menyemak, cek, cek. Dan sehingga ia di pihak yang benar kedudukan, kita jenis hanya masukkannya ke dalam kedudukan yang betul, yang mana nama asalnya. Jadi itu hanya algoritma, pseudokod per se, jenis, bagaimana kita akan melaksanakan satu jenis kemasukan. Pseudokod ada di sini. Ia adalah semua dalam talian. Jangan bimbang jika anda semua cuba untuk menyalin ini ke bawah. Jadi sekali lagi, sama question-- apa akan menjadi yang terbaik dan paling teruk runtimes untuk jenis kemasukan? Ia hampir sama dengan soalan yang terakhir. Saya akan memberikan anda semua, seperti, 30 saat untuk berfikir tentang perkara ini juga. OK Adakah sesiapa yang mahu memberi saya masa jalan yang paling teruk? Yeah. PENONTON: n kuasa dua. ANDI PENG: Ia n kuasa dua. Dan mengapa ia n kuasa? PENONTON: Kerana dalam secara terbalik, anda perlu melalui n kali n, yang is-- ANDI PENG: Ya, betul-betul. Perkara Jadi sama seperti dalam bentuk gelembung. Jika senarai ini adalah dalam urutan, anda akan mempunyai untuk memeriksa sekali pertama. Dan kemudian dengan setiap nilai tambahan, anda akan mempunyai untuk memeriksa terhadap setiap nilai tunggal, bukan? Dan sebagainya sama sekali, anda akan membuat yang kali n pas lain n lulus, yang adalah n kuasa dua. Bagaimana pula dengan kes ini? Yeah. PENONTON: n tolak 1, kerana Yang pertama sudah kuasa dua. ANDI PENG: Jadi, dekat. Jawapannya adalah sebenarnya n. Kerana manakala yang pertama adalah disusun, ia mungkin tidak actually-- ia kita hanya lucked keluar, contoh tersebut, yang 2 berlaku untuk menjadi nombor yang paling kecil. Tetapi itu tidak akan sentiasa menjadi kes itu. Jika 2 sudah disusun pada mulanya tetapi anda kelihatan dan ada 1 di sini, 1 akan bertemu ia. Dan ia akan berakhir sehingga yang terserempak anyways. Jadi dalam kes senario yang terbaik, ia sebenarnya hanya akan menjadi n. Jika anda mempunyai 1, 2, 3, 4, 5, 6, 7, 8, anda akan berjalan melalui bahawa seluruh senarai sekali untuk memeriksa untuk melihat jika kuatir. Adakah semua orang jelas mengenai berjalan kali pemilihan juga? Saya tahu saya akan melalui ini benar-benar cepat. Tetapi hanya tahu bahawa jika anda tahu konsep umum, anda perlu baik. OKAY. Jadi saya hanya akan memberikan anda semua mungkin, seperti, satu minit untuk bercakap dengan jiran-jiran anda kepada apa yang hanya beberapa daripada perbezaan utama antara jenis kejayaannya. Kami akan pergi tidak lama lagi. PENONTON: Oh, OK. ANDI PENG: Ya. OKAY. Cool, mari kita bergabung semula sebagai kelas. OKAY. Jadi ini adalah jenis yang soalan terbuka dalam erti kata bahawa ada banyak jawapan kepada mereka. Dan kita akan pergi ke beberapa daripada mereka secara ringkas. Saya hanya mahu untuk mendapatkan anda semua berfikir tentang apa yang dibezakan ketiga-tiga jenis kejayaannya. Dan aku mendengar, juga, yang besar question-- apakah bergabung jenis lakukan? Soalan yang besar, kerana itulah apa yang kita meliputi akan datang. Jadi bergabung apapun adalah satu jenis yang berfungsi sangat berbeza daripada jenis lain. Seperti yang anda semua boleh see-- Nabi Daud melakukan demo yang di mana beliau mempunyai semua sejuk bunyi melihat bagaimana bergabung semacam berlari, seperti, tak terhingga lebih cepat daripada dua jenis yang lain? OKAY. Jadi itu kerana merge semacam melaksanakan jurang yang dan menakluk konsep yang kami telah bercakap tentang banyak dalam kuliah. Dalam pengertian itu yang kita suka bekerja lebih bijak, bukan lebih keras, apabila anda membahagikan dan menakluk masalah, dan memecahkan mereka ke bawah, dan kemudian meletakkan mereka bersama-sama, yang baik-baik selalu berlaku. Jadi cara yang bergabung jenis dasarnya berfungsi ialah ia membahagikan satu lokasi terisih pada separuh. Dan kemudian ia mendapat dua bahagian tatasusunan. Dan ia hanya menyusun kedua-dua bahagian. Ia hanya menyimpan membahagikan dua, dalam separuh, pada separuh sehingga semuanya disusun dan kemudian secara rekursif meletakkan semua bersama-sama. Jadi, itu benar-benar abstrak. Jadi ini adalah hanya sedikit kod pseudo. Adakah ini masuk akal dalam cara ia berjalan? Jadi mari kita hanya mengatakan anda mempunyai yang pelbagai n unsur, bukan? Jika n adalah kurang daripada 2, anda boleh kembali. Kerana anda tahu bahawa jika ada hanya satu perkara, ia mesti disusun. Lain, anda menyusun separuh kiri, dan kemudian anda menyusun separuh yang betul, dan kemudian anda bergabung. Oleh itu, sambil yang kelihatan benar-benar mudah, pada hakikatnya, berfikir tentang ia jenis sukar. Kerana anda seperti, baik, itu adalah jenis yang berjalan pada dirinya. Betul? Ia berjalan ke atas dirinya. Jadi dalam erti kata itu, David menyentuh kepada rekursi di dalam kelas. Dan itulah konsep yang kita akan bercakap tentang banyak lagi. Ia yang ini, kedua-dua baris di sini, sebenarnya hanya program ini memberitahu ia berjalan sendiri dengan input yang berbeza. Jadi, daripada berjalan sendiri dengan keseluruhan daripada n elemen, anda boleh memecahkan ia turun ke dalam separuh kiri dan separuh yang betul dan kemudian berjalan lagi. Dan kemudian kita akan melihat ia secara visual, kerana saya seorang pelajar visual. Ia berfungsi lebih baik untuk saya. Oleh itu, kita akan melihat satu contoh visual di sini. Katakan kita mempunyai array, enam elemen, 3, 5, 2, 6, 4, 1, tidak disusun. Baiklah, ada banyak di laman ini. Jadi jika anda semua boleh melihat langkah pertama di sini, 3, 5, 2, 6, 4, 1, anda boleh berpecah kepada dua bahagian. Anda mempunyai 3, 5, 2, 6, 4, 1. Anda tahu bahawa ini aren't-- anda tidak tahu jika mereka disusun atau tidak, supaya anda terus pecahkan ke bawah, pada separuh, pada separuh, pada separuh, sehingga akhirnya, anda hanya mempunyai satu elemen. Dan salah satu elemen sentiasa disusun, bukan? Jadi kita tahu bahawa 3, 5, 2, 4, 6, 1, dengan diri mereka sendiri, sedang disusun. Dan sekarang kita boleh meletakkan mereka kembali bersama-sama. Jadi kita tahu 3, 5. Kami meletakkan mereka bersama-sama. Kita tahu bahawa yang disusun. 2 ini masih ada. Kita boleh meletakkan 4 dan 6 bersama-sama. Kita tahu bahawa yang yang disusun, jadi kami meletakkan bahawa bersama-sama. Dan 1 ada. Dan kemudian anda hanya melihat kedua-dua bahagian di sini. Anda mempunyai 3, 5, 2, 2, 3, 5. Anda hanya boleh membandingkan bermula segala-galanya. Kerana anda tahu bahawa ini disusun dan anda tahu bahawa yang yang disusun. Oleh itu, maka anda tidak perlu membandingkan 5, anda hanya bandingkan 3. Dan 2 adalah kurang dari 3, maka anda tahu 2 mesti pergi pada akhirnya. Perkara yang sama di sana. 1 mesti pergi sini. Dan kemudian apabila anda pergi untuk meletakkan kedua-dua nilai-nilai bersama-sama, anda tahu bahawa ini adalah disusun dan anda tahu bahawa yang disusun. Sebab itu 1 dan 2, 1 adalah kurang dari 2. Yang memberitahu anda bahawa 1 perlu pergi pada akhir ini tanpa melihat 3 atau 5. Dan kemudian 4, anda boleh hanya menyemak, ia pergi betul-betul di sini. Anda tidak perlu melihat 5. Perkara yang sama dengan 6. Anda tahu bahawa ia hanya 6-- tidak perlu diberi perhatian. Dan supaya dengan cara itu, anda hanya menyelamatkan diri banyak langkah-langkah apabila anda membandingkan. Anda tidak perlu membandingkan setiap elemen terhadap unsur-unsur lain. Anda hanya membandingkan terhadap orang-orang yang yang anda perlu membandingkan ia menentang. Jadi itulah jenis konsep abstrak. Jangan bimbang jika ia tidak agak memukul anda betul-betul lagi. Tetapi secara umumnya, ini adalah bagaimana merge berfungsi. Soalan, soalan yang cepat, sebelum saya bergerak? Yeah. PENONTON: Jadi, anda berkata bahawa anda mengambil 1, dan kemudian 4, dan 6 dan memasukkannya ke dalam. Jadi tidak those-- tidak anda melihat mereka unsur-unsur berasingan, tidak secara keseluruhannya ini? ANDI PENG: Ya. Jadi apa yang berlaku adalah bahawa anda pada dasarnya mencipta pelbagai jenama baru. Jadi, anda tahu bahawa, di sini, saya mempunyai dua tatasusunan saiz 3, bukan? Jadi, anda tahu bahawa pelbagai disusun saya perlu mempunyai enam elemen. Jadi anda hanya membuat kadar baru ingatan. Jadi anda jenis seperti membazir ingatan, tetapi itu tidak penting kerana ia adalah sangat kecil. Jadi, anda melihat 1 dan anda melihat 2. Dan anda tahu bahawa 1 adalah kurang dari 2. Jadi, anda tahu bahawa 1 perlu pergi dalam permulaan semua daripada mereka. Anda tidak perlu melihat 3 dan 5. Jadi, anda tahu 1 pergi ke sana. Kemudian anda pada dasarnya memenggal 1. Ia adalah, seperti, mati kepada kami. Maka kita hanya perlu 2, 3, 5, dan kemudian 4 dan 6. Dan kemudian anda tahu itu, anda membandingkan 4 dan 2, oh, yang 2 perlu pergi di sana. Jadi, anda mencebur 2 bawah, anda mencincang off. Sebab itu anda hanya perlu 3 dan 5 dalam 4 dan 6. Dan anda hanya menyimpan mencincang ia di luar sehingga memasukkannya ke dalam array. PENONTON: Jadi anda hanya sentiasa membandingkan [didengar]? ANDI PENG: Tepat sekali. Jadi dalam erti kata itu, anda berada hanya membandingkan, pada dasarnya, satu nombor terhadap nombor yang lain. Dan kerana anda tahu bahawa ia disusun, anda tidak perlu melihat melalui semua nombor. Anda hanya perlu untuk melihat yang pertama. Dan kemudian anda hanya boleh mencebur mereka ke bawah, kerana anda tahu mereka tergolong di mana mereka perlu tergolong. Yeah. Soalan yang baik. Dan kemudian sesiapa di antara kamu agak bercita-cita tinggi, berasa bebas untuk melihat kod ini. Ini sebenarnya adalah pelaksanaan fizikal bagaimana kita akan menulis merge. Dan anda boleh lihat, ia adalah sangat singkat. Tetapi idea-idea di sebalik ia adalah agak kompleks. Jadi, jika anda merasa seperti lukisan ini keluar di malam ini kerja rumah anda, jangan ragu untuk. OKAY. Lalu Daud juga telah pergi lebih ini dalam kuliah. Apakah kes ini runtimes, runtimes kes paling teruk, dan runtimes diharapkan daripada jenis merge? Beberapa saat untuk berfikir. Ini adalah agak sukar, tetapi jenis intuitif jika anda berfikir mengenainya. Baiklah. PENONTON: Apakah yang paling teruk kes n log n? ANDI PENG: Tepat sekali. Dan mengapa ia n log n. PENONTON: tidak Adakah kerana ia menjadi pesat lebih cepat, jadi ia seperti satu fungsi yang bukan hanya sekadar menjadi n kuasa dua atau sesuatu? ANDI PENG: Tepat sekali. Jadi sebab mengapa runtime mengenai perkara ini ialah n log n adalah because-- apakah anda lakukan dalam semua langkah-langkah ini? Anda hanya memotong ia pada separuh, bukan? Dan supaya apabila kita melakukan log, semua yang ia lakukan membahagikan masalah pada separuh, pada separuh, pada separuh, lebih banyak bahagian. Dan dalam erti kata itu, anda boleh jenis untuk menghapuskan model linear yang kita telah menggunakan. Kerana apabila anda mencincang perkara yang pada separuh, ia log. Itu hanya matematik cara yang mewakili mereka. Dan kemudian akhirnya, pada akhirnya, anda berada hanya membuat satu pas lepas melalui untuk meletakkan semua daripada mereka untuk, bukan? Dan jadi jika anda hanya perlu menyemak satu perkara, itu n. Dan supaya anda jenis mendarabkan bersama-sama kedua-dua. Jadi ia adalah seperti anda telah mendapat yang akhir periksa n down sini dengan log n di sini. Dan jika anda membiak mereka, itu n log n. Dan supaya kes dan paling teruk yang terbaik kes dan dijangka semua n log n. Ia juga seperti jenis lain. Ia seperti jenis pemilihan dalam erti kata bahawa ia Tidak kira apa yang anda senarai adalah, ia hanya akan untuk melakukan perkara yang sama setiap kali tunggal. OKAY. Jadi seperti yang anda semua boleh lihat, walaupun macam yang kita telah pergi through-- n kuasa dua, ia tidak sangat cekap. Dan juga ini n log n adalah bukan yang paling cekap. Jika anda semua ingin tahu, ada mekanisme jenis yang begitu berkesan bahawa mereka hampir dasarnya rata dalam masa jalanan. Anda telah mendapat beberapa log n. Anda telah mendapat beberapa log log n. Kami tidak menyentuh mereka dalam kelas ini buat masa ini. Tetapi jika anda semua ingin tahu, sila google, apa yang mekanisme menyusun paling berkesan. Saya tidak tahu, terdapat beberapa yang benar-benar lucu, like-- ada beberapa benar-benar yang lucu yang orang membuat. Dan anda tertanya-tanya bagaimana mereka pernah terfikir untuk itu. Jadi google, jika anda mempunyai beberapa lapang semasa, atas, apa yang adalah beberapa cara lucu yang dan kaum serta orang ways-- cekap telah dapat melaksanakan pelbagai. OKAY. Dan di sini hanya satu carta sedikit berguna. Saya tahu anda semua, sebelum itu kuiz 0, akan berada di dalam bilik anda mungkin cuba menghafal itu. Jadi itulah yang bagus di sana untuk anda semua. Hanya jangan lupa logik yang dibuat- mengapa nombor-nombor tersebut telah berlaku. Jika anda selalu hilang, hanya membuat pasti anda tahu apa yang macam berada. Dan anda boleh berjalan melalui mereka dalam fikiran anda untuk memahami mengapa mereka jawapan jawapan-jawapan tersebut. Baiklah. Oleh itu, kita akan bergerak pada, akhirnya, untuk pencarian. Kerana sebagai Pelawat yang telah membaca pset, pencarian juga merupakan sebahagian daripada masalah ini minggu ini menetapkan. Anda akan diminta untuk melaksanakan dua jenis carian. Satu adalah carian linear dan satu adalah carian binari. Jadi carian linear adalah agak mudah. Anda hanya ingin mencari elemen dalam senarai untuk melihat jika anda mendapatkannya. Anda hanya perlu untuk melelar melalui. Dan jika ia sama dengan sesuatu, anda hanya boleh kembali itu, bukan? Tetapi satu yang kita paling berminat untuk bercakap tentang adalah carian binari, kanan, yang merupakan membahagi dan menakluk mekanisme yang Daud menunjukkan dalam kuliah. Ingat contoh buku telefon yang dia terus membesarkan, salah satu yang dia jenis bergelut sedikit pada tahun lalu, di mana anda membahagikan masalah pada separuh, pada separuh, pada separuh, lagi dan lagi, sehingga anda mencari apa yang anda cari? Dan anda telah mendapat runtime daripada itu juga. Dan anda boleh lihat, ia ketara lebih berkesan daripada apa-apa jenis carian. Jadi cara yang kita akan pergi tentang melaksanakan carian binari adalah, jika kita mempunyai array, indeks 0-6, tujuh elemen, kita boleh melihat di tengah-tengah, right-- maaf, jika soalan kami first-- jika kita ingin bertanya soalan, adakah array mengandungi elemen 7, jelas, menjadi manusia, dan mempunyai seperti pelbagai kecil, ia adalah mudah bagi kita untuk mengatakan ya. Tetapi cara untuk melaksanakan binari carian adalah untuk melihat di tengah-tengah. Kita tahu bahawa indeks 3 adalah tengah-tengah, kerana kita tahu terdapat tujuh elemen. Apa 7 dibahagikan dengan 2? Anda boleh meneka bahawa tambahan 1. Anda telah mendapat 3 di tengah-tengah. Begitu juga dengan pelbagai 3 sama dengan 7? Ia tidak, bukan? Tetapi kita boleh melakukan beberapa cek. Adalah pelbagai daripada 3 kurang daripada 7 atau adalah pelbagai daripada 3 lebih besar daripada 7? Dan kita tahu bahawa ia adalah kurang daripada 7. Oleh itu, kita tahu bahawa, oh, ia mesti tidak berada dalam separuh kiri. Kita tahu bahawa ia mesti pada separuh yang betul, bukan? Oleh itu, kita hanya boleh meneka separuh array. Kita tidak perlu melihat lagi. Kerana kita tahu bahawa separuh daripada problem-- kami kita tahu bahawa jawapan itu adalah dalam separuh kanan masalah kita. Oleh itu, kita hanya melihat bahawa sekarang. Jadi sekarang kita melihat pertengahan apa yang tinggal. Bahawa indeks 5. Kami melakukan pemeriksaan yang sama sekali lagi dan kita melihat bahawa ia adalah lebih kecil. Oleh itu, kita melihat di sebelah kiri itu. Dan kemudian kita melihat daftar itu. Apakah nilai keselesaan dan kemudahan di Indeks 4 sama dengan 7? Ia adalah. Oleh itu, kita boleh kembali benar, kerana kami mendapati nilai dalam senarai kami. Adakah cara yang saya lalui yang masuk akal untuk semua orang? OKAY. Saya akan memberikan anda semua mungkin, seperti, tiga, empat minit untuk memikirkan bagaimana untuk pseudokod ini. Jadi bayangkan Saya bertanya kepada anda untuk menulis fungsi dipanggil carian () yang pulang nilai, nilai Boolean, itu adalah benar atau false-- seperti, benar jika anda mendapati nilai, palsu jika anda tidak. Dan kemudian anda adalah diluluskan pada nilai yang anda cari ke dalam nilai-nilai, yang adalah array-- oh, saya pasti meletakkan bahawa di tempat yang salah. OKAY. Anyways, yang sepatutnya pernah ke kanan nilai. Dan kemudian int n ialah bilangan elemen dalam array itu. Bagaimana anda pergi tentang mencuba kepada kod pseudo bahawa masalah dalam? Saya akan memberikan anda semua suka tiga minit untuk berbuat demikian. Tidak, saya fikir ada only-- yeah, ada satu betul di sini. PENONTON: Bolehkah saya? ANDI PENG: Ya, saya mendapat anda. Adakah kerja itu? OK, sejuk. OKAY. Semua lelaki betul, kita berada akan mengekang dalam. OKAY. Jadi menganggap kita telah mendapat ini indah sedikit pelbagai dengan nilai-nilai n di dalamnya. Saya tidak menarik garis. Tetapi bagaimana kita akan pergi tentang cuba untuk menulis ini? Adakah sesiapa yang mahu memberi saya baris pertama? Jika anda ingin memberi saya Baris pertama pseudokod ini. PENONTON: [didengar] PENONTON: Anda akan mahu untuk melelar through-- PENONTON: Hanya satu lagi untuk gelung? PENONTON: --Untuk. ANDI PENG: Jadi yang ini agak rumit. Fikirkan about-- anda mahu terus berjalan gelung ini lagi dan lagi sehingga bila? PENONTON: Sehingga [didengar] nilainya sama dengan nilai itu. ANDI PENG: Tepat sekali. Jadi, anda boleh sebenarnya hanya write-- kita juga boleh memudahkan lebih. Kami hanya boleh melakukan gelung sementara, bukan? Jadi anda hanya boleh mempunyai loop-- kita tahu bahawa itu seketika. Tetapi untuk sekarang, saya akan untuk mengatakan "gelung" - melalui apa? Loop until-- apa yang keadaan berakhir kita? Saya rasa saya mendengarnya. Saya mendengar seseorang mengatakan ia. PENONTON: Nilai-nilai sama tengah. ANDI PENG: Katakan sekali lagi. PENONTON: Atau, sehingga nilai yang anda sedang mencari adalah sama dengan nilai tengah. ANDI PENG: Bagaimana jika ia tidak di sana? Bagaimana jika nilai yang anda sedang mencari untuk tidak sebenarnya dalam pelbagai ini? PENONTON: Anda kembali 1. ANDI PENG: Tetapi apa yang kita mahu gelung sehingga jika kita mempunyai keadaan? Yeah. PENONTON: Sehingga terdapat hanya satu nilai? ANDI PENG: Anda boleh gelung until-- supaya anda tahu bahawa anda akan mempunyai nilai max, bukan? Dan anda tahu bahawa anda akan mempunyai nilai min, bukan? Kerana juga, itu sesuatu Saya terlupa untuk mengatakan sebelum ini, bahawa sesuatu yang kritikal mengenai carian binari adalah bahawa pelbagai anda sudah disusun. Oleh kerana tidak ada cara untuk berbuat ini jika mereka nilai-nilai hanya secara rawak. Anda tidak tahu jika seseorang itu lebih besar dari yang lain, bukan? Jadi, anda tahu yang anda dan max minit anda berada di sini, bukan? Jika anda akan dapat menyesuaikan diri max anda dalam minit anda dan mid-- mari kita hanya menganggap anda nilai pertengahan adalah sini-- betul anda akan pada dasarnya gelung sehingga minimum anda lebih kurang sama dengan maks anda, kanan, atau jika maks anda tidak sama seperti min anda. Betul? Kerana apabila itu berlaku, anda tahu bahawa anda telah akhirnya mencecah nilai yang sama. Jadi, anda mahu gelung sehingga min anda adalah kurang daripada atau sama supaya- oops, tidak kurang daripada atau sama dengan, dengan cara yang lain around-- max. Adakah ini masuk akal? Saya mengambil beberapa cuba untuk mendapatkan hak itu. Tetapi gelung sehingga nilai maksimum anda pada dasarnya hampir kurang daripada atau sama dengan minimum anda, bukan? Itulah apabila anda tahu yang anda telah berkumpul. PENONTON: Apabila akan maksimum anda nilai kurang daripada minimum? ANDI PENG: Jika anda menyimpan menyesuaikan ia, yang adalah apa yang kita akan untuk melakukan dalam hal ini. Adakah ini masuk akal? Minimum dan maksimum hanya integer yang kita mungkin akan mahu untuk mencipta untuk menjaga mengesan di mana kita cari. Kerana array wujud tidak kira apa yang kita lakukan. Seperti, kita tidak benar-benar secara fizikal pancung array, bukan? Kami hanya menyesuaikan di mana kita cari. Adakah ini masuk akal? PENONTON: Ya. ANDI PENG: OK. Jadi jika itu syarat untuk gelung kami, apa yang kita mahu di dalam gelung ini? Apa yang kita akan mahu lakukan? Jadi sekarang, kita telah mendapat max dan min, betul, mungkin dicipta di sini suatu tempat. Kami akan mungkin mahu untuk mencari yang pertengahan, bukan? Bagaimana kita akan menjadi dapat mencari tengah-tengah? Apa yang mathematical-- yang PENONTON: Max ditambah min dibahagikan dengan 2. ANDI PENG: Tepat sekali. Adakah ini masuk akal? Dan yang anda semua nampak mengapa kita tidak hanya use-- mengapa kita lakukan ini daripada melakukan hanya n dibahagikan dengan 2? Ini kerana n adalah nilai yang yang akan tetap sama. Betul? Tetapi seperti yang kita menyesuaikan minimum dan nilai maksimum, mereka akan berubah. Dan hasilnya, tengah kami akan berubah. Jadi itulah sebabnya kita mahu untuk berbuat baik ini di sini. OKAY. Dan kemudian, sekarang kami telah mendapati our-- yeah. PENONTON: Hanya question-- cepat apabila anda mengatakan min dan max, kita menganggap bahawa ia sudah disusun? ANDI PENG: Ya, itu sebenarnya satu pra-syarat untuk carian binari, yang perlu anda tahu ia disusun. Itulah sebabnya jenis, anda menulis dalam anda masalah set sebelum carian binari anda. OKAY. Jadi sekarang kita tahu di mana titik tengah kami ini, apa yang anda mahu lakukan di sini? PENONTON: Kami mahu membandingkan yang kepada orang lain. ANDI PENG: Tepat sekali. Jadi, anda akan membandingkan pertengahan kepada nilai, bukan? Dan apa yang memberitahu kita apabila kita bandingkan? Apa yang kami mahu lakukan selepas itu? PENONTON: Jika nilai adalah lebih besar daripada pertengahan, kami mahu potong. ANDI PENG: Tepat sekali. Jadi, jika nilai yang lebih besar daripada pertengahan, kami akan mahu untuk mengubah minimum dan maxes, bukan? Apa yang kita mahu berubah? Jadi, jika kita tahu nilai adalah suatu tempat di sini, apa yang anda kita berubah? Kami mahu mengubah kami minimum untuk menjadi pertengahan, bukan? Kemudian lagi, jika ia dalam ini setengah, apa yang kita mahu berubah? PENONTON: maksimum anda. ANDI PENG: Ya. Dan kemudian anda hanya akan untuk menjaga menggelung, bukan? Kerana sekarang, selepas satu lelaran melalui, anda telah mendapat max di sini. Dan kemudian anda boleh mengira semula pertengahan a. Dan kemudian anda boleh membuat perbandingan. Dan anda akan terus pergi sehingga minit dan maxes telah pada dasarnya bertumpu. Dan itulah apabila anda tahu bahawa anda telah melanda akhir itu. Dan sama ada anda telah mendapati ia atau anda tidak mempunyai pada ketika itu. Adakah ini masuk akal untuk semua orang? OKAY. Ini adalah cukup penting, kerana anda akan mempunyai untuk menulis ini di malam ini kod anda. Tetapi anda semua mempunyai yang cukup baik rasa apa yang anda perlu lakukan, yang baik. OKAY. Jadi kami mempunyai kira-kira tujuh minit kiri bahagian. Jadi, kita akan bercakap tentang Serangga ini yang kita akan lakukan. Jadi Serangga dibahagikan kepada dua bahagian. Separuh pertama melibatkan melaksanakan find a di mana anda menulis carian linear, carian binari, dan algoritma yang sorting. Jadi ini adalah yang pertama masa dalam pset mana kami akan memberikan anda semua apa yang dipanggil kod pengedaran, yang merupakan kod bahawa kita mempunyai pra-bertulis, tetapi hanya meninggalkan beberapa keping off untuk anda untuk menyelesaikan secara bertulis. Jadi anda semua, apabila anda melihat ini kod, anda mungkin akan benar-benar takut. Jika anda hanya suka, ahh, saya tidak tahu apa yang yang demikian, Saya tidak tahu, seperti, yang seolah-olah begitu rumit, ahh, berehat. Tidak mengapa. Baca spesifikasi. Spec akan menerangkan kepada anda dengan tepat apa semua program-program ini lakukan. Sebagai contoh, generate.c adalah program yang yang akan datang dengan pset anda. Anda sebenarnya tidak perlu menyentuh, tetapi anda perlu memahami apa yang ia lakukan. Dan generate.c, semua yang ia lakukan adalah memuat menjana nombor rawak atau anda boleh memberikan keturunan, seperti nombor yg telah diatur sebelumnya bahawa ia mengambil masa, dan ia menjana lebih nombor. Jadi ada cara yang khusus untuk melaksanakan generate.c di mana anda hanya boleh membuat sekumpulan nombor untuk anda untuk menguji kaedah anda yang lain pada. Jadi, jika anda mahu, untuk Sebagai contoh, menguji find anda, anda akan mahu menjalankan generate.c, menjana sekumpulan nombor, dan kemudian berjalan fungsi pembantu anda. Fungsi pembantu anda adalah di mana anda berada sebenarnya fizikal menulis kod. Dan memikirkan pembantu sebagai fail perpustakaan anda menulis find yang memanggil. Dan demikian dalam helpers.c, anda akan melakukan mencari dan menyusun. Dan kemudian anda akan pada dasarnya hanya meletakkan mereka semua bersama-sama. Spec ini akan memberitahu anda bagaimana untuk meletakkan bahawa pada baris arahan. Dan anda akan dapat untuk menguji sama ada atau tidak menyusun dan carian anda bekerja. Sejuk. Adakah sesiapa pun bermula dan masalah yang dihadapi atau soalan mereka mempunyai sekarang dengan ini? OKAY. PENONTON: Tunggu. Saya ada satu soalan. ANDI PENG: Ya. PENONTON: Jadi saya mula melakukan carian linear dalam helpers.c dan ia tidak benar-benar bekerja. Tetapi kemudian, saya mendapat tahu kita hanya perlu memadamnya dan melakukan carian binari. Jadi adakah ia perkara jika ia tidak berfungsi? ANDI PENG: Jawapan pendek tidak. Tetapi oleh kerana kita tidak-- PENONTON: Tetapi tidak ada yang sebenarnya memeriksa. ANDI PENG: Kami tidak pernah akan melihat bahawa. Tetapi anda mungkin ingin memastikan carian anda berfungsi. Kerana jika anda linear carian tidak berfungsi, maka kemungkinan binari anda carian tidak akan berfungsi dengan baik. Kerana anda perlu sama logik dalam kedua-dua mereka. Dan tidak, ia tidak benar-benar perkara itu. Jadi satu-satunya anda akan bertukar dalam adalah jenis dan carian binari. Yeah. Dan juga, banyak anak-anak adalah cuba untuk menyusun helpers.c. Anda sebenarnya tidak dibenarkan untuk berbuat demikian, kerana helpers.c tidak mempunyai fungsi utama. Dan supaya anda hanya boleh menjadi benar-benar menyusun menjana dan mencari, kerana mencari panggilan helpers.c dan fungsi-fungsi di dalamnya. Supaya membuat debugging sakit di punggung itu. Tetapi itulah yang perlu kita lakukan. PENONTON: Anda hanya membuat semua, bukan? ANDI PENG: Anda boleh hanya membuat semua juga, ya. OKAY. Jadi itu sahaja dari segi apa yang pset meminta anda semua lakukan. Jika anda mempunyai sebarang pertanyaan, sila untuk bertanya kepada saya selepas seksyen. Saya akan berada di sini untuk, seperti, 20 minit. Dan yeah, yang pset ini benar-benar tidak yang buruk. Kalian harus OK. Ini, ikuti garis panduan. Jenis mempunyai rasa, secara logiknya, apa sepatutnya berlaku dan anda akan selamat. Jangan terlalu takut. Ada banyak kod lagi menulis di sana. Jangan terlalu takut jika tidak memahami apa yang semua yang bermakna. Jika ia banyak, ia benar-benar baik. Dan datang ke waktu pejabat. Kami akan membantu anda membaca. PENONTON: Dengan tambahan fungsi, kita melihat mereka sehingga? ANDI PENG: Ya, mereka adalah dalam kod. Dalam permainan 15, separuh daripada ia telah ditulis untuk anda. Maka orang-orang fungsi adalah sudah dalam kod. Ya. Baiklah. Nah, selamat mencuba. Ia adalah hari yang menjijikkan. Jadi diharapkan anda semua tidak akan merasa begitu susah tinggal di dalam dan pengkodan.