[MUSIC PLAYING] 

ANDI PENG: Selamat Datang di minggu 3 bagian. Terima kasih, kalian, untuk semua datang untuk ini sebelumnya waktu mulai hari ini. Kami punya bagus, sedikit Kelompok intim hari ini. Jadi mudah-mudahan kita akan mendapatkan selesai, mungkin, awal, sedikit sedikit lebih awal hari ini. Begitu cepat, hanya beberapa pengumuman untuk agenda hari ini. Sebelum kita mulai, kami akan hanya pergi beberapa masalah logistik singkat, pset pertanyaan, menanyai, hal-hal seperti itu. Dan kemudian kita akan menyelam tepat di. Kami akan menggunakan debugger GDB untuk disebut mulai membongkar kode kita, yang David dijelaskan dalam ceramah hari lain. Kami akan pergi selama empat jenis macam. Kami akan pergi atas mereka cukup cepat karena mereka cukup intensif. Tapi tahu bahwa semua slide dan kode sumber selalu online. Jadi jangan ragu, di teliti, untuk kembali dan lihatlah itu. 

Kami akan pergi melalui notasi asimtotik, yang hanya cara mewah mengatakan "runtimes," di mana kita memiliki O besar, yang David menjelaskan dalam kuliah. Dan kami juga memiliki Omega, yang adalah runtime terikat lebih rendah. Dan kita akan berbicara sedikit lebih mendalam tentang bagaimana mereka bekerja. Dan terakhir, kita akan pergi lebih dari pencarian biner, karena banyak yang telah Anda melirik psets Anda mungkin tahu bahwa itu adalah pertanyaan yang ada di pset Anda. Jadi Anda semua akan senang bahwa kita menutupi hari ini. 

Dan terakhir, per Anda bagian umpan balik, aku benar-benar meninggalkan sekitar 15 menit pada akhirnya hanya pergi logistik pset3, pertanyaan, mungkin sedikit bimbingan, jika Anda mau, sebelum kita mulai pemrograman. Jadi mari kita coba untuk melewati bahan cukup cepat. Dan kemudian kita bisa menghabiskan beberapa waktu mengambil lebih banyak pertanyaan untuk pset tersebut. OKE. 

Cepat, sehingga hanya beberapa pengumuman sebelum kita mulai hari ini. Pertama, selamat datang untuk membuat melalui dua psets Anda. Aku mengambil melihat your-- yeah, mari kita mendapatkan tepuk tangan untuk yang satu. Sebenarnya, aku benar-benar, benar-benar terkesan. Saya dinilai yang pset pertama untuk kalian minggu dan Anda lalu kalian lakukan luar biasa. 

Gaya adalah pada titik selain beberapa komentar. Pastikan Anda selalu komentar kode Anda. Tapi psets Anda berada di titik. Dan tetap up. Dan itu baik untuk anak kelas untuk melihat bahwa kalian menempatkan di banyak usaha dalam gaya Anda dan desain Anda dalam kode Anda bahwa kita ingin bagi Anda untuk melihat. Jadi aku melewati sepanjang terima kasih untuk sisa TA. 

Namun ada beberapa pertanyaan menanyai Aku hanya ingin pergi lebih dari itu akan membuat kedua hidupku dan banyak yang lain TA 'hidup sedikit lebih mudah. Pertama, saya perhatikan ini masa lalu week-- berapa banyak dari Anda telah berjalan check50 pada kode Anda sebelum Anda mengirimkan? OKE. Jadi setiap orang harus melakukan check50, because-- sebuah secret-- kita benar-benar menjalankan check50 sebagai bagian dari kebenaran kami script untuk menguji kode Anda. Jadi jika kode Anda gagal check50, kemungkinan besar, itu mungkin akan gagal kami cek juga. Kadang-kadang kalian memiliki jawaban yang tepat. Seperti, di serakah, beberapa Anda memiliki nomor yang tepat, Anda hanya mencetak beberapa hal ekstra. Dan bahwa hal ekstra sebenarnya gagal cek, karena komputer tidak benar-benar tahu apa itu cari. Dan sehingga hanya akan berjalan melalui, melihat bahwa output Anda tidak sesuai dengan apa yang kita harapkan jawabannya menjadi, dan menandainya salah. 

Dan aku tahu yang terjadi di beberapa kasus Anda minggu ini. Jadi aku kembali dan manual regraded kode semua orang. Di masa depan meskipun, silahkan, pastikan bahwa Anda menjalankan memeriksa 50 pada kode Anda. Karena itu jenis sakit untuk TA harus kembali dan manual regrade setiap pset tunggal untuk setiap tunggal, sedikit terjawab misalnya. Jadi saya tidak melepas poin. Saya pikir saya melepas mungkin satu atau dua untuk desain. Di masa depan meskipun, jika Anda gagal check50, poin akan diambil off untuk kebenaran. 

Selanjutnya, psets adalah karena Jumat pada siang hari. Saya pikir ada tujuh menit akhir masa tenggang bahwa kita memberikan. Per waktu Harvard, mereka diizinkan untuk tujuh menit terlambat untuk semuanya. Jadi di sini di Yale, kita akan mematuhi itu juga. Tapi cukup banyak, di 00:07, jika pset Anda tidak di, itu akan ditandai sebagai akhir. Dan sementara itu ditandai sebagai an, TA-- aku masih akan kadar psets Anda. Sehingga Anda masih akan melihat kelas yang muncul. Namun, tahu bahwa pada akhir semester, semua psets akhir hanya akan otomatis memusatkan perhatian oleh komputer. 

Kami melakukan ini karena dua alasan. Satu, kadang-kadang kita mendapatkan dimaafkan, seperti alasan dekan, nanti bahwa saya tidak tahu tentang belum. Jadi kami ingin memastikan bahwa kami sedang kadar semuanya hanya dalam kasus, seperti, aku hilang alasan seorang dekan. Dan kedua, perlu pikiran, Anda masih bisa menjatuhkan salah pset yang memiliki ruang lingkup poin penuh. Dan jadi kami ingin kelas semua psets Anda hanya memastikan bahwa ruang lingkup Anda ada dan Anda mencoba mereka. Jadi, bahkan jika terlambat, Anda masih akan mendapatkan kredit untuk poin lingkup, saya pikir. 

Jadi moral dari cerita ini adalah, membuat Pastikan psets Anda berada di tepat waktu. Dan jika mereka tidak dalam tepat waktu, tahu bahwa itu tidak besar. Ya, sebelum saya melanjutkan, apakah ada yang punya pertanyaan tentang tanggapan pset? Ya. 

AUDIENCE: Apakah Anda mengatakan kami bisa drop salah satu psets? 

ANDI PENG: Ya. Jadi ada sembilan psets keseluruhan selama semester. Dan jika Anda memiliki ruang lingkup points-- sehingga lingkup hanya, cukup banyak, yang Anda mencoba yang masalah, yang Anda menempatkan dalam waktu, yang Anda menunjukkan bahwa Anda telah menunjukkan Anda sudah membaca spec. Itu cukup banyak ruang lingkup. Dan jika Anda memenuhi poin lingkup, kami bisa drop terendah satu dari lingkup penuh. Jadi yang ada di keuntungan Anda untuk melengkapi dan mencoba setiap pset. 

Bahkan upload-- jika tidak ada mereka bekerja, meng-upload mereka semua. Dan kemudian kita mudah-mudahan akan dapat memberikan beberapa titik-titik kembali. Keren. Ada pertanyaan lain? Besar. 

Kedua, kantor hours-- beberapa catatan singkat tentang jam kantor. Jadi pertama, datang di awal minggu. Tidak ada yang pernah di jam kantor pada hari Senin. Christabel datang ke jam kantor tadi malam. Ya, Christabel. Dan apa yang kita miliki di kantor jam semalam, Christabel? 

AUDIENCE: Kami memiliki es krim. 

ANDI PENG: Jadi itu benar, kami memiliki es krim pada jam-jam kantor tadi malam. Sementara saya tidak bisa menjanjikan Anda bahwa kita akan memiliki es krim di jam kantor setiap minggu, apa yang bisa saya berjanji Anda adalah bahwa akan ada secara signifikan siswa yang lebih baik untuk rasio TA. Seperti legit, itu seperti 3-1. Padahal, kontras bahwa dengan Kamis, Anda punya sekitar 150 benar-benar menekankan anak-anak dan tidak ada es krim. Dan itu tidak produktif bagi siapa pun. Jadi moral dari cerita ini adalah, datang lebih awal untuk jam kantor dan hal-hal yang baik akan terjadi. 

Juga, datang siap untuk mengajukan pertanyaan. Kamu tahu? Terlepas dari apa TA, saya berpikir, telah mengatakan, kita sudah mendapatkan beberapa siswa yang datang pada hari Kamis di, seperti, 10:50 tidak membaca spec menjadi seperti membantu saya, membantu saya. Sayangnya pada saat itu, ada tidak banyak yang bisa kita lakukan untuk membantu Anda. Jadi silakan datang di awal minggu. Datang lebih awal untuk jam kantor. Ayo siap untuk mengajukan pertanyaan. Pastikan bahwa Anda, sebagai mahasiswa, yang mana Anda perlu sehingga TA dapat memandu Anda sepanjang, yang adalah apa jam kantor harus dialokasikan untuk. 

Kedua, jadi aku tahu profesor ingin mengejutkan kita dengan tes. Aku punya seorang profesor mereka seperti, yo, dengan cara, ingat paruh waktu yang Anda memiliki Senin depan. Ya, saya tidak tahu tentang ujian tengah semester itu. Jadi saya akan menjadi yang TA yang mengingatkan Anda semua kuis yang 0-- karena, kau tahu, kami CS. Sekarang kita sudah array dilakukan, Anda mendapatkan mengapa hal itu kuis 0, tidak kuis 1, eh? OKE. Oh, aku punya beberapa terkekeh yang satu itu. OKE. 

Jadi kuis 0 akan 14 Oktober jika Anda berada di bagian Senin-Rabu dan 15 Oktober jika Anda berada di bagian Selasa-Kamis. Ini tidak berlaku untuk Bagi Anda di Harvard who-- Saya pikir Anda semua akan mengambil kuis Anda pada tanggal 14. 

Jadi ya, minggu depan, jika David, dalam kuliah, pergi, yeah, jadi tentang itu kuis minggu depan, semua tidak akan terkejut karena Anda datang ke bagian dan Anda tahu bahwa Anda kuis 0 adalah dalam dua minggu. Dan kita akan memiliki review sesi dan segala sesuatu. Sehingga tidak ada kekhawatiran tentang yang takut untuk itu. Pertanyaan before-- pertanyaan sama sekali mengenai masalah logistik, grading, jam kantor, bagian? Ya. 

AUDIENCE: Jadi kuis ini akan selama kuliah? 

ANDI PENG: Ya. Jadi kuis, saya pikir, adalah 60 menit dialokasikan dalam slot waktu Anda hanya akan mengambil di ruang kuliah. Jadi Anda tidak perlu datang pada, seperti, acak 07:00. Itu semua baik. Ya. Keren. 

Baiklah. Jadi kita akan memperkenalkan konsep untuk Anda pekan ini bahwa David memiliki sudah jenis dari menyentuh dalam kuliah minggu terakhir ini. Ini disebut GDB. Dan berapa banyak dari Anda, sementara di kursus menulis psets Anda, telah melihat tombol besar yang mengatakan "Debug" pada bagian atas IDE Anda? OKE. Jadi sekarang kita benar-benar akan mendapatkan untuk menggali misteri apa tombol yang benar-benar tidak. Dan saya jamin, itu adalah indah, hal yang indah. 

Jadi sampai sekarang, saya pikir sudah ada dua hal siswa telah biasanya lakukan ketika debugging psets. Satu, mereka baik menambahkan printf () - sehingga setiap beberapa baris, mereka menambahkan dalam printf () - oh, apa variabel ini? Oh, apa variabel ini sekarang-- dan Anda jenis melihat perkembangan yang kode Anda seperti berjalan. Atau metode kedua anak-anak lakukan adalah bahwa mereka hanya menulis semuanya dan kemudian pergi seperti ini di akhir. Mudah-mudahan itu bekerja. Saya jamin, GDB lebih baik dari kedua metode tersebut. Ya. Jadi ini akan menjadi sahabat baru Anda. Karena itu adalah hal yang indah yang secara visual menampilkan kedua apa kode Anda lakukan pada titik tertentu serta apa semua Anda variabel membawa, seperti apa nilai-nilai mereka, pada titik tertentu. Dan dengan cara ini, Anda bisa benar-benar mengatur breakpoints dalam kode Anda. Anda dapat dijalankan melalui baris demi baris. Dan GDB hanya akan memiliki untuk Anda, ditampilkan untuk Anda, apa semua variabel Anda yang, apa yang mereka lakukan, apa yang terjadi dalam kode. Dan sedemikian rupa, itu jadi lebih mudah untuk melihat apa yang terjadi bukannya printf-ing atau menuliskan laporan Anda. 

Jadi kami akan melakukan contoh ini nanti. Jadi ini tampaknya sedikit abstrak. Jangan khawatir, kami akan melakukan contoh. Dan pada dasarnya, tiga terbesar, fungsi yang paling sering digunakan Anda harus di GDB Berikutnya adalah, Langkah lebih, dan Langkah ke tombol. Aku akan kepala ada, sebenarnya, sekarang. 

Jadi bisa kalian semua melihat bahwa atau saya harus memperbesar sedikit? Di bagian belakang, bisa Anda lihat itu? Haruskah saya memperbesar? Sedikit saja? OK keren. Di sana kami pergi. OKE. 

Jadi saya punya, di sini, saya implementasi untuk serakah. Dan sementara banyak dari kalian menulis serakah sementara lingkaran form-- yang adalah cara yang bisa diterima untuk melakukan itu-- cara lain untuk melakukannya adalah dengan hanya membagi dalam Modulo. Karena Anda dapat memiliki Anda nilai dan kemudian memiliki sisanya Anda. Dan kemudian Anda bisa hanya menambahkannya semua bersama-sama. Apakah logika apa yang saya lakukan di sini masuk akal untuk semua orang, sebelum kita mulai? Seperti? Keren. Besar. Itu sepotong yang cukup seksi kode, saya akan mengatakan. Seperti saya katakan, David, di kuliah, setelah beberapa saat, Anda semua akan mulai melihat kode sebagai sesuatu yang indah. Dan kadang-kadang ketika Anda melihat indah kode, itu seperti perasaan yang luar biasa. 

Jadi bagaimanapun, sementara kode ini sangat indah, itu tidak bekerja dengan benar. Jadi mari kita jalankan check50 ini. Periksa 50 20-- oop. 2? Apakah pset2 itu? Ya. Oh, pset1. OKE. Jadi kita jalankan check50. 

Dan seperti yang kalian lihat di sini, itu gagal beberapa kasus. Dan bagi sebagian dari Anda, dalam Tentu saja melakukan set masalah Anda, Anda seperti, ah, mengapa tidak bekerja. Mengapa bekerja untuk beberapa nilai tetapi tidak untuk orang lain? Nah, GDB akan membantu Anda sosok mengapa masukan mereka tidak bekerja. 

OKE. Jadi mari kita lihat, salah satu cek aku gagal di check50 adalah nilai masukan dari 0,41. Jadi jawaban yang benar yang Anda harus mendapatkan adalah 4. Tapi bukannya apa yang saya mencetak adalah 3-n, yang tidak benar. Jadi mari kita jalankan ini secara manual, hanya memastikan bahwa check50 bekerja. Mari kita lakukan ./greedy. Ups, saya harus membuat serakah. Di sana kami pergi. Sekarang ./greedy. 

Berapa banyak yang berutang? Mari kita lakukan 0,41. Dan yep, kita lihat di sini bahwa itu keluaran 3 ketika jawaban yang benar, pada kenyataannya, harus 4. Jadi mari kita masukkan GDB dan melihat bagaimana kami bisa pergi tentang memperbaiki masalah ini. 

Jadi langkah pertama dalam selalu debugging kode Anda adalah untuk mengatur breakpoint, atau titik di mana Anda ingin komputer atau debugger untuk mulai melihat. Jadi, jika Anda tidak benar-benar tahu apa masalah Anda, biasanya, hal khas kita ingin lakukan adalah untuk mengatur breakpoint kami di utama. Jadi jika kalian bisa melihat ini tombol merah di sana, yep, yang saya menetapkan breakpoint untuk fungsi utama. Saya klik itu. 

Dan kemudian saya bisa pergi ke tombol Debug saya. Aku menekan tombol itu. Biarkan aku tampilannya kembali jika saya bisa. Di sana kami pergi. Jadi kita miliki, di sini, sebuah panel di sebelah kanan. Maaf, orang di belakang, Anda tidak bisa benar-benar melihat dengan sangat baik. Tapi pada dasarnya, semua panel kanan ini adalah melakukan adalah melacak kedua disorot line, yang merupakan baris kode bahwa komputer saat ini berjalan, serta semua variabel Anda dibawah sini. 

Jadi Anda punya sen, koin, n, semua dinyatakan hal yang berbeda pada pokoknya. Jangan khawatir, karena kita belum benar-benar diinisialisasi mereka untuk variabel apa pun. Jadi di komputer Anda, Anda komputer hanya melihat, oh, 32.767 adalah fungsi yang terakhir digunakan itu ruang memori di komputer saya. Dan di situlah sen saat ini. Tapi tidak bahwa setelah Anda menjalankan kode, itu harus menjadi diinisialisasi. 

Jadi mari kita pergi melalui, baris demi line, apa yang terjadi di sini. OKE. Jadi di sini adalah tiga tombol yang saya hanya menjelaskan. Anda memiliki Play, atau fungsi Run, tombol, Anda memiliki tombol Langkah lebih, dan Anda juga memiliki Langkah ke tombol. Dan pada dasarnya, semua tiga mereka hanya pergi melalui kode Anda dan melakukan hal-hal yang berbeda. 

Jadi biasanya, ketika Anda debugging, kita tidak ingin hanya memukul Play, karena Putar hanya akan berjalan kode Anda untuk akhir itu. Dan kemudian Anda tidak akan benar-benar tahu apa masalah Anda kecuali Anda mengatur beberapa breakpoints. Jika Anda menetapkan beberapa breakpoints, itu hanya akan otomatis berlari dari satu breakpoint, ke depan, ke yang berikutnya. Tapi dalam kasus ini kita sudah hanya satu itu, karena kita ingin bekerja dengan cara kami dari atas ke bawah. Jadi kita akan mengabaikan tombol yang sekarang untuk tujuan program ini. 

Jadi Langkah atas fungsi hanya langkah lebih setiap baris dan memberitahu Anda apa komputer lakukan. Langkah ke dalam fungsi berjalan ke dalam fungsi yang sebenarnya yang ada di baris Anda kode. Jadi misalnya, seperti printf (), yang fungsi, kan? Jika saya ingin secara fisik langkah ke dalam printf () fungsi, Aku akan benar-benar pergi ke sepotong kode di mana printf () ditulis dan melihat Apa yang sedang terjadi di sana. 

Tapi biasanya, kita berasumsi bahwa kode yang kami berikan Anda bekerja. Kami menganggap printf () bekerja. Kami berasumsi bahwa getInt () bekerja. Jadi tidak perlu untuk melangkah ke fungsi-fungsi. Tetapi jika ada fungsi yang Anda tulis sendiri yang Anda ingin memeriksa apa yang terjadi, Anda akan ingin melangkah ke dalam fungsi itu. 

Jadi sekarang kita hanya akan melangkahi potongan kode ini. Jadi mari kita lihat. Oh, cetak, "Oh hai, bagaimana banyak perubahan yang berutang? " Kami tidak peduli. Kita tahu bahwa bekerja, jadi kita melangkah di atasnya. 

Jadi n, yang mengambang kami yang kita sudah initialized-- atau declared-- di atas, kita sekarang menyamai bahwa untuk GetFloat (). Jadi mari kita melangkah lebih dari itu. Dan kita lihat pada bawah sini, program mendorong saya untuk memasukkan nilai. Jadi mari kita masukan nilai yang kita inginkan untuk menguji di sini, yang merupakan 0,41. Besar. 

Jadi sekarang n-- yang kalian lihat di sini, di bottom-- itu stored-- karena kita belum bulat belum, itu disimpan dalam raksasa seperti ini mengambang yang ,4099999996, yang cukup dekat dengan kami tujuan, sekarang, untuk 0,41. Dan kemudian kita akan lihat nanti, seperti yang kita terus melangkahi program, setelah di sini, n telah menjadi bulat dan sen menjadi 41. Besar. Jadi kita tahu bahwa kerja pembulatan kita. Kita tahu bahwa kita memiliki jumlah yang benar dari sen, sehingga kita tahu bahwa itu tidak benar-benar masalah. 

Jadi kami terus melangkah di dalam program ini. Kami pergi di sini. Dan jadi setelah baris kode ini, kita harus tahu berapa banyak tempat yang kita miliki. Kita melangkah lebih. Dan Anda melihat kami, pada kenyataannya, memiliki satu kuartal karena kami telah dikurangi 25 dari nilai awal kami 41. Dan kami memiliki 16 kiri untuk sen kami. 

Apakah semua orang mengerti bagaimana program ini melangkah melalui dan mengapa sen kini telah menjadi 16 dan mengapa, sekarang, koin telah menjadi 1? Apakah semua orang mengikuti logika itu? Keren. Sehingga dari titik ini, kerja program, kan? Kami tahu itu melakukan persis apa yang kita inginkan. Dan kita tidak benar-benar harus mencetak, oh, apa adalah sen pada titik ini, apa koin pada saat ini. 

Kami terus akan melalui program. Langkah selesai. Keren. Kami pergi dime. Besar. Kita melihat bahwa itu diambil off $ 0,10 untuk sepeser pun. Dan sekarang kami memiliki dua koin. Itu benar. 

Kami pergi ke uang dan kami melihat bahwa kita sudah mendapat tersisa sen. Hmm, itu aneh. Sampai di sini di program ini, saya seharusnya telah dikurangi uang saya. Mungkin aku hanya tidak melakukan itu garis kanan. Dan sayangnya, Anda dapat melihat di sini, karena kita tahu bahwa kita melangkah melalui jalur 32 dan 33, situlah program kami benar memiliki variabel menjalankan. Jadi kita dapat melihat dan melihat, oh, Saya mengurangkan sen di sini, tapi aku tidak benar-benar menambah nilai koin saya. Saya menambahkan untuk sen. Dan aku tidak ingin menambah sen, saya ingin menambah koin. Jadi jika kita mengubah itu untuk koin, kami punya program kerja. Saya bisa menjalankan check50. Anda hanya dapat keluar dari GDB tepat di sini dan kemudian jalankan check50 lagi. Aku hanya bisa melakukan ini. Saya harus membuat serakah. 0.41. Dan di sini, itu printing keluar jawaban yang benar. 

Sehingga kalian bisa lihat, GDB adalah alat yang sangat kuat ketika kita memiliki begitu banyak kode terjadi dan begitu banyak variabel bahwa sulit bagi kami, karena manusia, untuk melacak. Komputer, dalam GDB debugger, memiliki kemampuan untuk melacak segala sesuatu. Aku tahu, di Visionaire, kalian mungkin mungkin telah memukul beberapa kesalahan segmentasi karena Anda sedang berlari di luar batas dari array Anda. Dalam contoh Caesar, yang persis apa yang saya telah menerapkan sini. 

Jadi saya lupa untuk memeriksa apa yang akan terjadi jika saya tidak memiliki dua argumen baris perintah. Aku hanya tidak dimasukkan ke dalam cek. Dan jadi jika saya menjalankan Debug-- saya set breakpoint saya ke kanan ada. Saya menjalankan Debug. 

OKE. Ya. Jadi sebenarnya, GDB seharusnya telah mengatakan kepada saya ada adalah kesalahan segmentasi ada. Aku tidak tahu apa yang sedang terjadi di sana, tapi ketika aku berlari itu, itu bekerja. Ketika Anda menjalankan baris kode melalui dan GDB mungkin saja tiba-tiba berhenti pada Anda, naik dan melihat apa kesalahan merah. Ini akan memberitahu Anda, hei, Anda memiliki kesalahan segmentasi, yang berarti bahwa Anda mencoba untuk mengakses ruang dalam array yang tidak ada. Ya. 

Jadi dalam masalah berikutnya set minggu ini, kalian mungkin akan memiliki banyak variabel mengambang sekitar. Anda tidak akan menjadi yakin apa mereka semua berarti pada titik tertentu. Jadi GDB akan sangat membantu Anda dalam mencari apa mereka semua menyamai dan mampu melihat bahwa secara visual. Apakah ada yang bingung tentang bagaimana semua itu bekerja? Keren. Baiklah. Jadi setelah itu, kita akan menyelam tepat ke empat yang berbeda jenis macam untuk minggu ini. Berapa banyak dari Anda, pertama tama, sebelum kita mulai, telah membaca seluruh spec untuk pset3? OKE. Aku bangga kalian. Itu seperti setengah dari kelas, yang secara signifikan lebih dari terakhir kali. 

Jadi itu bagus, karena ketika kita berbicara tentang isi di lecture-- atau menyesal, di section-- Saya suka untuk berhubungan banyak yang kembali ke apa pset adalah dan bagaimana Anda ingin menerapkan bahwa dalam pset Anda. Jadi, jika Anda datang memiliki membaca spec, itu akan menjadi jauh lebih mudah bagi Anda untuk memahami apa yang saya bicarakan ketika saya mengatakan, oh hey, mungkin ini benar-benar tempat yang baik untuk melaksanakan semacam ini. Jadi bagi anda yang telah membaca spek tahu bahwa, sebagai bagian dari pset Anda, Anda akan harus menulis jenis macam. Jadi ini mungkin sangat membantu untuk banyak hari ini. 

Jadi kita akan mulai dengan, dasarnya, jenis yang paling sederhana semacam, semacam seleksi. Algoritma khas untuk bagaimana kita akan pergi tentang ini is-- David pergi melalui ini semua di kuliah, jadi saya cepat akan bergerak sepanjang sini-dasarnya, Anda memiliki sebuah array nilai. Dan kemudian Anda menemukan Nilai disortir terkecil dan Anda swap yang nilai dengan nilai disortir pertama. Dan kemudian Anda hanya terus mengulangi dengan sisa daftar Anda. 

Dan inilah penjelasan visual yang bagaimana yang akan bekerja. Jadi misalnya, jika kita mulai dengan array lima elemen, indeks 0-4, dengan 3, 5, 2, 6, dan 4 nilai-nilai ditempatkan di array-- sehingga sekarang, kami hanya akan menganggap bahwa mereka semua disortir karena kita belum diuji sebaliknya. 

Jadi bagaimana semacam seleksi akan kerja adalah bahwa hal itu akan pertama dijalankan melalui keseluruhan yang dari array disortir. Ini akan memilih nilai terkecil. Dalam hal ini, 3, tepat sekarang, adalah yang terkecil. Sampai ke 5. Tidak, 5 tidak lebih besar than-- atau maaf, tidak kurang than-- 3. Jadi nilai minimum masih 3. Dan kemudian Anda bisa 2. Komputer melihat, oh, 2 kurang dari 3. 2 sekarang harus nilai minimum. Dan 2 swap dengan nilai pertama. 

Jadi setelah satu lulus, kita memang melihat bahwa 2 dan 3 tertukar. Dan kami hanya akan terus melakukan ini lagi dengan sisa array. Jadi kita akan jalankan melalui empat indeks terakhir array. Kita akan melihat bahwa 3 adalah nilai minimum berikutnya. Jadi kita akan menukar itu dengan 4. Dan kemudian kita hanya akan terus berjalan melalui sampai, akhirnya, Anda sampai ke array diurutkan di mana 2, 3, 4, 5, dan 6 semua diurutkan. Apakah setiap orang memahami logika bagaimana semacam seleksi bekerja? 

Anda hanya memiliki semacam dari nilai minimum. Anda melacak apa itu. Dan setiap kali Anda menemukannya, Anda swap dengan nilai pertama di array-- yang atau, bukan value-- pertama nilai berikutnya dalam array. Keren. 

Sehingga kalian jenis melihat dari sekilas singkat, kita akan pseudocode ini. Jadi jika kalian di belakang ingin membentuk kelompok, semua orang di meja dapat membentuk mitra kecil, aku akan untuk memberikan orang-orang seperti tiga menit hanya berbicara melalui logika, dalam bahasa Inggris, bagaimana kita mungkin bisa menerapkan pseudocode untuk menulis semacam seleksi. Dan ada permen. Silahkan datang dan mendapatkan permen. Jika Anda berada di belakang dan Anda ingin permen, aku bisa melemparkan permen pada Anda. Sebenarnya, lakukan keren you--. Oh maaf. OKE. 

Jadi jika kita ingin, sebagai kelas, menulis pseudocode bagaimana mungkin satu pendekatan masalah ini, hanya merasa bebas. Aku hanya akan pergi berkeliling dan, dalam rangka, meminta kelompok untuk baris berikutnya apa yang harus kita lakukan. Jadi jika kalian ingin memulai off, apa hal pertama yang harus dilakukan ketika Anda mencoba untuk menerapkan cara untuk memecahkan program ini selektif memilah daftar? Mari kita asumsikan kita memiliki sebuah array, oke? 

AUDIENCE: Anda ingin membuat beberapa semacam [tak terdengar] bahwa Anda berjalan melalui seluruh array Anda. 

ANDI PENG: Benar. Jadi Anda akan ingin beralih melalui setiap ruang, kan? Sangat bagus. Jika kalian ingin memberi saya selanjutnya line-- yeah, di belakang. 

AUDIENCE: Memeriksa mereka semua untuk yang terkecil. 

ANDI PENG: Ada kita pergi. Jadi kami ingin pergi melalui dan memeriksa untuk melihat apa nilai minimum, kan? Aku akan menyingkat ke "min." Apa yang kalian ingin lakukan setelah Anda telah menemukan nilai minimum? 

AUDIENCE: [tidak terdengar] ANDI PENG: Jadi Anda akan ingin beralih dengan yang pertama dari array, benar? Itu awalnya, aku akan mengatakan. Baiklah. Jadi sekarang bahwa Anda telah bertukar pertama satu, apa yang Anda ingin lakukan setelah itu? Jadi sekarang kita tahu bahwa satu ini di sini harus menjadi nilai terkecil, kan? Maka Anda memiliki sisa tambahan dari array yang tidak dipisahkan. Jadi apa yang ingin Anda lakukan di sini, jika Anda orang ingin memberikan baris berikutnya? AUDIENCE: Jadi Anda ingin iterate melalui sisa array. ANDI PENG: Ya. Dan jadi apa iterasi melalui jenis menyiratkan kita mungkin perlu? Jenis of-- apa 

AUDIENCE: Oh, variabel tambahan? ANDI PENG: Mungkin lain untuk loop, kan? Jadi kita mungkin akan ingin iterate through-- besar. Dan kemudian Anda akan kembali dan mungkin memeriksa minimum lagi, benar? Dan Anda akan terus mengulangi ini, karena loop hanya akan untuk terus berjalan, kan? 

Sehingga kalian bisa lihat, kita hanya memiliki pseudo umum bagaimana kita ingin program ini untuk mencari. Iterate ini di sini, apa yang kita lakukan biasanya perlu menulis dalam kode kami jika kita ingin iterate melalui array, apa jenis struktur? Saya pikir Christabel sudah mengatakan ini sebelumnya. 

AUDIENCE: A untuk loop. 

ANDI PENG: A untuk loop? Tepat. Jadi ini mungkin akan menjadi untuk loop. Apa cek di sini akan menyiratkan? Biasanya, jika Anda ingin memeriksa jika ada sesuatu yang sesuatu else-- 

AUDIENCE: Jika. 

ANDI PENG: Sebuah jika, kan? Dan kemudian swap sini, kita akan pergi kemudian, karena David pergi melalui bahwa dalam kuliah juga. Dan kemudian iterate kedua implies-- 

AUDIENCE: lain untuk loop. 

ANDI PENG: --another untuk loop, persis. Jadi jika kita cari ini benar, kita dapat melihat bahwa kita mungkin akan membutuhkan bersarang untuk loop dengan pernyataan kondisional dalam ada dan kemudian sepotong sebenarnya kode itu akan menukar nilai-nilai. Jadi saya baru saja umumnya ditulis kode pseudo sini. Dan kemudian kita benar-benar akan secara fisik, sebagai kelas, mencoba untuk menerapkan hari ini. Mari kita kembali ke IDE ini. 

Uh oh. Kenapa begitu not-- ada itu. OKE. Maaf, saya mencoba untuk memperbesar sedikit lebih. Di sana kami pergi. Semua yang saya lakukan di sini adalah saya buat sebuah program yang disebut "seleksi / sort.c." Saya telah membuat sebuah array dari sembilan nilai-nilai, 4, 8, 2, 1, 6, 9, 7, 5, 3. Saat ini, yang Anda bisa lihat, mereka unordered. n akan menjadi nomor yang memberitahu Anda jumlah nilai Anda memiliki dalam array Anda. Dalam hal ini, kita memiliki sembilan nilai. Dan saya baru saja mendapat untuk loop di sini yang mencetak array disortir. 

Dan pada akhirnya, saya juga punya untuk loop yang hanya print keluar lagi. Jadi secara teoritis, jika program ini bekerja dengan benar, pada akhirnya, Anda akan melihat dicetak untuk loop di mana 1, 2, 3, 4, 5, 6, 7, 8, 9 semua benar agar. 

Jadi kita punya pseudo kami di sini. Apakah ada yang ingin to-- aku hanya akan pergi meminta volunteers-- ceritakan apa untuk mengetik jika kami ingin, pertama, hanya iterate melalui awal array ini? Apa baris kode saya mungkin akan butuhkan di sini? 

AUDIENCE: [tidak terdengar] 

ANDI PENG: Ya, merasa gratis to-- maaf, Anda tidak harus berdiri nuansa up-- bebas untuk meningkatkan suara Anda sedikit. 

AUDIENCE: Untuk int i sama 0-- 

ANDI PENG: Ya, baik. 

AUDIENCE: i kurang dari panjang array. 

ANDI PENG: Jadi perlu keberatan di sini, karena kami tidak memiliki fungsi yang memberitahu kita panjang array, kita sudah memiliki nilai yang menyimpan itu. Benar? Satu hal yang perlu di mind-- dalam array dari sembilan nilai, apa indeks? Anggap saja array ini adalah 0-3. Anda melihat bahwa yang terakhir Indeks sebenarnya 3. Ini bukan 4, meskipun ada empat nilai dalam array. 

Jadi di sini, kita harus sangat berhati-hati apa kondisi kita untuk panjang akan menjadi. 

AUDIENCE: Bukankah n minus 1? ANDI PENG: Ini akan n minus 1, persis. Apakah itu masuk akal, mengapa itu n minus 1, setiap orang? Itu karena array adalah nol-diindeks. Mereka mulai 0 dan berjalan sampai n minus 1. Ya, itu sedikit rumit. OKE. Dan kemudian-- AUDIENCE: Isnt'1 yang sudah diurus meskipun, dengan hanya tidak mengatakan "kurang dari atau sama dengan "dan hanya mengatakan" kurang dari? " 

ANDI PENG: Itu Pertanyaan benar-benar baik. Jadi iya. Tapi juga, cara yang kami melaksanakan hak memeriksa, Anda perlu membandingkan dua nilai. Jadi Anda benar-benar ingin meninggalkan "untuk" kosong. Karena jika Anda membandingkan yang satu ini, Anda tidak akan memiliki apa-apa setelah itu untuk membandingkan, kan? Ya. Jadi i ++. Mari menambahkan kurung kami di. Whoops. Besar. Jadi kita memiliki awal loop luar kita. Jadi sekarang kita mungkin ingin membuat variabel untuk menjaga track dari nilai terkecil, kan? Apakah ada yang ingin memberi saya baris kode yang akan melakukan itu? Apa yang kita butuhkan jika kita akan ingin menyimpan sesuatu? 

Benar. Mungkin nama yang lebih baik untuk itu akan be-- "temp" benar-benar works-- mungkin lebih tepat bernama akan, jika kita ingin value-- terkecil 

AUDIENCE: Min. ANDI PENG: min, ada kita pergi. min akan baik. Dan jadi di sini, apa yang kita lakukan ingin menginisialisasi ke? Ini adalah sedikit rumit. Karena sekarang di mulai dari array ini, Anda belum melihat apa-apa, kan? Jadi apa, secara otomatis, jika kami hanya pada i sama dengan 0, apa yang kita ingin menginisialisasi nilai minimum pertama kita ke? AUDIENCE: i. ANDI PENG: i, persis. Christabel, mengapa kita ingin untuk menginisialisasi ke saya? 

AUDIENCE: Karena, baik, kita mulai dengan 0. Jadi karena kita punya apa-apa untuk membandingkan untuk, minimal akan berakhir menjadi 0. 

ANDI PENG: Tepat. Jadi dia tepat. Karena kita tidak benar-benar memandang apa pun, kita tidak tahu apa nilai minimum kami adalah. Kami hanya ingin menginisialisasi ke i, yang, saat ini, ada di sini. Dan seperti yang kita terus bergerak ke bawah array ini, kita akan melihat bahwa, dengan masing-masing tambahan lulus, saya akan menambahkan. Dan pada saat itu, i mungkin akan ingin menjadi minimum, karena itu akan menjadi apa pun adalah awal dari array disortir. Keren. 

Jadi sekarang kita ingin menambahkan untuk loop di sini itu akan iterate melalui disortir, atau sisa array ini. Apakah ada yang ingin memberi saya baris kode yang akan melakukan itu? Hint-- apa yang kita butuhkan di sini? Apa yang akan masuk ini untuk loop? Ya. AUDIENCE: Jadi kita akan ingin memiliki bilangan bulat yang berbeda, karena kita berjalan melalui sisanya dari array bukan saya, jadi mungkin j. 

ANDI PENG: Ya, j terdengar baik padaku. Sama? 

AUDIENCE: Jadi akan saya ditambah 1, karena Anda mulai di nilai berikutnya. Dan kemudian ke end-- jadi lagi, j adalah kurang dari n minus 1, dan kemudian j ++. ANDI PENG: Great. 

Dan kemudian di sini, kita akan ingin untuk memeriksa untuk melihat apakah kondisi kita terpenuhi, benar? Karena Anda ingin mengubah nilai minimum jika itu benar-benar lebih kecil dari apa yang Anda membandingkannya dengan, kan? Jadi apa yang akan kita inginkan dalam sini? Periksa untuk melihat. Apa jenis pernyataan kita mungkin akan ti ingin menggunakan jika kita ingin memeriksa sesuatu? 

AUDIENCE: Sebuah jika pernyataan. 

ANDI PENG: Sebuah jika pernyataan. Jadi if-- dan apa yang akan menjadi kondisi yang kita inginkan dalam dari jika pernyataan kita? 

AUDIENCE: Jika nilai j kurang dari nilai Aku-- 

ANDI PENG: Tepat. Jadi if-- jadi array ini disebut "array." Besar. Jadi jika array-- apa itu? Katakan itu lagi. 

AUDIENCE: Jika array-j kurang dari array i, maka kita akan mengubah min. Jadi min akan j. 

ANDI PENG: Apakah itu masuk akal? OKE. Dan sekarang di sini, kita benar-benar ingin menerapkan swap, kan? Jadi ingat, dalam kuliah, bahwa David, ketika ia berusaha untuk swap the-- apa yang jus jeruk itu-- dan milk-- 

AUDIENCE: Itu kotor. 

ANDI PENG: Ya, itu agak kotor. Tapi itu cukup bagus Konsep menunjukkan waktu. Jadi pikirkan nilai-nilai Anda di sini. Anda punya sebuah array min, array i, atau apa pun kita mencoba untuk swap sini. Dan Anda mungkin tidak dapat tuangkan ke satu sama lain pada saat yang sama, kan? Jadi apa yang akan kita perlu untuk membuat di sini untuk menukar nilai-nilai benar? 

AUDIENCE: Sebuah variabel sementara. 

ANDI PENG: Sebuah variabel sementara. Jadi mari kita lakukan int temp. Lihat, ini akan menjadi lebih baik waktu to-- whoa, apa itu? OKE. Jadi ini akan menjadi lebih baik waktu untuk nama variabel "temp." Jadi mari kita lakukan int temp. Apa yang akan kita mengatur suhu sama dengan di sini? AUDIENCE: Min? ANDI PENG: Ini agak rumit. Ini sebenarnya tidak masalah pada akhirnya. Tidak peduli apa Agar Anda memilih untuk swap di asalkan Anda memastikan Anda melacak apa yang Anda swapping. 

AUDIENCE: Ini bisa menjadi array i. 

ANDI PENG: Ya, mari kita lakukan array i. Dan kemudian apa baris berikutnya kode kita ingin miliki di sini? AUDIENCE: array-i sama dengan array j. ANDI PENG: Dan terakhir? AUDIENCE: array-j sama dengan berbagai-i. AUDIENCE: Atau array j equals array temp-- atau, temp. 

ANDI PENG: OK. Jadi mari kita jalankan ini dan melihat jika itu akan bekerja. Dimana yang terjadi? Oh, itu masalah. Lihat, pada baris 40, kita mencoba untuk menggunakan array j? Tapi mana j hanya ada di? 

AUDIENCE: Dalam untuk loop. ANDI PENG: Benar. Jadi apa yang akan kita lakukan? 

AUDIENCE: Tentukan luar the-- AUDIENCE: Ya, saya rasa Anda harus menggunakan lain jika pernyataan, kan? Jadi seperti, jika minimum-- yang semua benar, biarkan aku berpikir. 

ANDI PENG: Guys, coba untuk melihat Mari lihat, apa yang bisa kita lakukan di sini? 

AUDIENCE: OK. Jadi jika minimum tidak sama j-- jadi jika minimum masih Aku-- maka kita tidak perlu menukar. 

ANDI PENG: Apakah itu sama saya? Apa yang Anda ingin katakan di sini? 

AUDIENCE: Atau ya, jika minimum tidak saya tidak sama, ya. ANDI PENG: OK. Nah yang memecahkan, jenis, masalah kita. Tapi itu masih tidak memecahkan masalah apa yang terjadi jika j-- sejak j tidak ada di luar itu, apa Anda yang ingin kita lakukan dengan itu? Mendeklarasikan luar? Mari kita coba jalankan ini. Uh oh. Semacam kami tidak bekerja. 

Seperti yang Anda lihat, kami awal Array memiliki nilai-nilai. Dan setelah itu harus memiliki berada di 1, 2, 3, 4, 5, 6, 7, 8, 9. Ini tidak bekerja. Ahh. Apa yang kita lakukan? AUDIENCE: Debug. ANDI PENG: Baiklah, kita dapat mencoba itu. Kami bisa debug. Zoom out sedikit. Mari kita mengatur breakpoint kami. Mari kita pergi like-- OK. 

Jadi karena kita sudah tahu bahwa garis-garis ini, 15 sampai 22, yang working-- karena semua saya lakukan adalah hanya iterasi melalui dan printing-- Aku bisa pergi ke depan dan melewatkan itu. Mari kita mulai dari garis 25. Oop, biarkan aku menyingkirkan itu. 

AUDIENCE: Jadi breakpoint ini mana debugging dimulai? ANDI PENG: Atau berhenti. AUDIENCE: Atau berhenti. ANDI PENG: Ya. Anda dapat mengatur beberapa breakpoints dan itu hanya bisa melompat dari satu ke yang lain. Tapi dalam kasus ini kita tidak tahu di mana kesalahan yang terjadi. Jadi kami hanya ingin mulai dari atas ke bawah. Yep. OKE. 

Jadi baris ini di sini, kita dapat melangkah di. Anda dapat melihat di sini, kita punya array. Mereka adalah nilai-nilai yang dalam array. Apakah Anda melihat bahwa, bagaimana indeks 0, itu sesuai dengan value-- oh, Aku akan mencoba untuk memperbesar. Maaf, itu benar-benar sulit untuk see-- di indeks array 0, kami memiliki nilai 4 dan kemudian sebagainya dan sebagainya. Kami memiliki variabel lokal kami. Sekarang saya adalah sama dengan 0, yang kita inginkan. 

Dan jadi mari kita terus melangkah melalui. Minimum kami adalah sama dengan 0, yang kami juga ingin menjadi. Dan kemudian kita masukkan kedua kami untuk lingkaran, jika array-j kurang dari array i, yang itu tidak. Jadi apakah Anda melihat bagaimana yang dilewati lebih dari itu? 

AUDIENCE: Jadi seharusnya jika minimum, semua itu-- tidak harus yang berada di dalam yang pertama untuk loop? ANDI PENG: Tidak, karena Anda masih ingin menguji. Anda ingin melakukan perbandingan setiap waktu, bahkan setelah Anda berjalan melalui itu. Anda tidak hanya ingin melakukannya pada pertama pass-through. Anda ingin melakukannya dengan setiap lulus tambahan lagi. Jadi, Anda ingin memeriksa kondisi Anda di dalam. Jadi kita hanya akan terus berjalan lewat sini. Saya akan memberikan kalian petunjuk. Ini ada hubungannya dengan fakta bahwa ketika Anda sedang memeriksa bersyarat Anda, Anda tidak memeriksa untuk indeks yang benar. Jadi sekarang Anda sedang memeriksa untuk Indeks array j kurang dari array yang indeks i. Tapi apa yang Anda lakukan di awal untuk loop? Apakah Anda tidak menetapkan j sama dengan saya? 

Ya, jadi kita benar-benar dapat keluar debugger di sini. Jadi mari kita lihat pseudocode kami. For-- kita akan mulai dari i sama dengan 0. Kita akan pergi ke n minus 1. Mari kita periksa, apakah kita memiliki hak itu? Ya, itu benar. 

Jadi dalam sini, kami akan menciptakan nilai minimum dan menetapkan bahwa sama dengan saya. Apakah kita melakukan itu? Yap, melakukan itu. Sekarang dalam batin untuk loop kami, kami akan melakukan j sama saya ke n 1 dikurangi. Apakah kita melakukan itu? Memang, kami melakukan itu. 

Jadi bagaimanapun, apa yang kita membandingkan di sini? 

AUDIENCE: j ditambah 1. ANDI PENG: Tepat. Dan kemudian Anda akan ingin mengatur minimum Anda sama dengan j ditambah 1 juga. Jadi saya pergi melalui yang benar-benar cepat. Apakah kalian mengerti mengapa j ditambah 1? OKE. 

Jadi dalam array, di lulus pertama Anda melalui, Anda untuk loop, untuk int i sama dengan 0, mari kita menganggap ini belum berubah belum. Kami memiliki sebuah array, benar-benar, hanya empat elemen disortir, kan? Jadi kita ingin menginisialisasi saya sama dengan 0. Dan saya akan hanya dijalankan melalui lingkaran ini. Dan di lulus pertama, kita akan untuk menginisialisasi sebuah variabel yang disebut "min" yang juga sama dengan saya, karena kita tidak memiliki nilai minimum. Jadi itulah saat sama dengan 0 juga. Dan kemudian kita akan pergi melalui. Dan kami ingin beralih lagi. Sekarang kita telah menemukan apa yang minimum kami adalah, kami ingin iterate melalui lagi untuk melihat apakah itu membandingkan, kan? Jadi j, di sini, akan untuk i sama, yaitu 0. Dan kemudian jika j berbagai plus saya, yang adalah salah satu yang selanjutnya lebih, kurang dari apa yang minimum saat Nilai adalah, Anda ingin menukar. 

Jadi mari kita hanya mengatakan kita sudah punya, seperti, 2, 5, 1, 8. Sekarang, saya adalah sama dengan 0 dan j sama dengan 0. Dan itulah nilai minimum kami. Jika array-j ditambah Aku-- sehingga jika satu itu setelah salah satu kita sedang melihat lebih besar dari yang sebelumnya itu, itu akan menjadi minimum. 

Jadi di sini kita melihat bahwa 5 tidak kurang dari itu. Jadi itu akan tidak 5. Kita melihat bahwa 1 kurang dari 2, kan? Jadi sekarang kita tahu bahwa minimum kami adalah akan menjadi nilai indeks pada 0, 1, 2. Ya? Dan kemudian ketika Anda mendapatkan di sini, Anda dapat menukar nilai-nilai yang benar. 

Jadi ketika kalian hanya memiliki j sebelumnya, Anda tidak melihat satu setelah itu. Anda sedang melihat nilai yang sama, yang mengapa hal itu tidak melakukan apa-apa. Apakah itu masuk akal untuk semua orang, mengapa kita membutuhkan itu ditambah 1 ada? OKE. Sekarang mari kita jalankan melalui itu untuk membuat Pastikan sisa kode sudah benar. Mengapa itu terjadi? Ah, itu adalah min di sini. Kami membandingkan nilai yang salah. Oh tidak. 

Oh ya, di sini kami menukar nilai yang salah juga. Karena kami sedang mencari di i dan j. Mereka adalah orang-orang kami memeriksa. Kami benar-benar ingin menukar minimum, minimum saat ini, dengan apa pun yang luar. Dan seperti yang kalian dapat melihat ke bawah di sini, kami memiliki array diurutkan. Itu hanya ada hubungannya dengan fakta bahwa ketika kami memeriksa nilai kami membandingkan, kami tidak melihat nilai-nilai yang tepat. Kami sedang mencari di satu sama sini, tidak benar-benar swapping itu. Anda harus melihat satu berikutnya untuk itu dan kemudian Anda dapat swap. Jadi itulah yang agak mengganggu kode kita sebelumnya. Dan apa yang saya lakukan di sini adalah segalanya debugger bisa dilakukan untuk Anda Saya hanya melakukannya pada papan, karena lebih mudah untuk melihat daripada mencoba untuk memperbesar debugger. Apakah itu masuk akal untuk semua orang? Keren. 

Baiklah. Kita bisa beralih ke berbicara tentang notasi asimtotik, yang adalah cara mewah mengatakan runtimes dari semua jenis ini. Jadi saya tahu David, dalam kuliah, disinggung runtimes. Dan ia pergi melalui seluruh rumus bagaimana menghitung runtimes. Jangan khawatir tentang itu. Jika Anda benar-benar ingin tahu bagaimana yang bekerja, merasa bebas untuk berbicara dengan saya setelah bagian. Kita bisa berjalan melalui rumus bersama-sama. Tapi semua kalian harus benar-benar tahu adalah bahwa n kuadrat lebih dari 2 adalah hal yang sama seperti n kuadrat. Karena jumlah terbesar, eksponen, tumbuh paling. Dan untuk tujuan kita, semua kita peduli adalah bahwa jumlah raksasa yang tumbuh. 

Jadi apa adalah kasus terbaik runtime seleksi semacam? Jika Anda akan memiliki iterate melalui daftar dan kemudian iterate melalui sisa daftar itu, berapa kali adalah Anda akan mungkin, di case-- terburuk di kasus terbaik, sorry-- dijalankan melalui? Mungkin pertanyaan yang lebih baik adalah bertanya, apa kasus terburuk runtime seleksi semacam. AUDIENCE: n kuadrat. ANDI PENG: Ini n kuadrat, benar. Jadi cara mudah untuk memikirkan ini seperti, setiap kali Anda memiliki dua bersarang untuk loop, itu akan n kuadrat. Karena bukan saja Anda berjalan melalui sekali lagi, Anda harus kembali sekitar dan berjalan melalui itu sekali lagi dalam untuk setiap nilai. Jadi dalam hal ini, Anda menjalankan n kali n kuadrat, yang is-- maaf, n kali n, yang equals n kuadrat. 

Dan semacam ini juga sedikit unik dalam arti bahwa tidak masalah jika ini nilai-nilai yang sudah dalam rangka. Ini masih akan berjalan melalui anyways. Anggap saja ini adalah 1, 2, 3, 4. Terlepas dari apakah atau tidak itu adalah di order, itu masih akan berlari melalui dan masih memeriksa nilai minimum. Ini akan membuat jumlah yang sama cek setiap saat, bahkan jika itu tidak benar-benar menyentuh apa pun. 

Jadi dalam kasus seperti itu, yang terbaik dan terburuk runtimes sebenarnya setara. Jadi runtime yang diharapkan seleksi semacam, yang kami menunjuk dengan simbol theta, theta, dalam hal ini, juga akan n kuadrat. Semua tiga ini akan n kuadrat. Apakah setiap orang yang jelas tentang mengapa runtime n kuadrat? 

Baiklah. Jadi aku hanya akan cepat menjalankan melalui sisa macam. Algoritma untuk gelembung sort-- ingat, ini adalah yang pertama David pergi dalam kuliah. Pada dasarnya, Anda melangkah melalui seluruh daftar dan Anda swap-- Anda hanya membandingkan dua pada satu waktu. Dan jika salah satu yang lebih besar, daripada Anda hanya swap mereka. Jadi jika ini adalah lebih besar, Anda akan menukar. Aku punya resmi di sini. 

Jadi katakan saja Anda memiliki 8, 6, 4, 2. Anda akan membandingkan 8 dan 6. Anda akan perlu untuk swap mereka. Anda akan membandingkan 8 dan 4. Anda akan perlu untuk swap mereka. Jika Anda harus menukar 8 dan 2, mengubah mereka juga. Jadi dalam arti seperti itu, Anda dapat melihat, dimainkan selama periode waktu yang panjang, bagaimana nilai-nilai semacam gelembung untuk ujungnya, itulah sebabnya kami menyebutnya bubble sort. 

Kami hanya akan dijalankan melalui lagi pada lulus kedua kami, dan lulus ketiga kami, dan lulus keempat kami. Pada dasarnya, bubble sort hanya berjalan sampai Anda tidak membuat swap lebih. Jadi dalam hal ini, ini hanya pseudocode umum untuk itu. Jangan khawatir, ini semua akan online. Kami tidak harus benar-benar pergi ini. 

Kami hanya menginisialisasi counter variabel yang dimulai pada 0. Dan kita iterate melalui seluruh array. Dan jika salah satu nilai is-- jika ini nilai lebih besar dari nilai tersebut, Anda akan swap mereka. Dan kemudian Anda hanya akan terus berjalan. Dan kau akan menghitung. Dan Anda hanya akan terus melakukan ini sementara counter lebih besar dari 0, yang berarti bahwa setiap kali Anda harus swap, Anda tahu bahwa Anda ingin pergi kembali dan periksa lagi. Anda ingin menyimpan memeriksa sampai Anda tahu Anda tidak perlu menukar lagi. 

Jadi apa yang terbaik dan terburuk kasus runtimes untuk bubble sort? Dan hint-- ini sebenarnya berbeda dari pemilihan semacam dalam arti bahwa kedua jawaban yang tidak sama. Pikirkan tentang apa yang akan terjadi di kasus jika itu sudah diurutkan. Dan berpikir tentang apa akan terjadi jika itu dalam kasus di mana itu tidak diurutkan. Dan Anda dapat jenis lari melalui mengapa yang terjadi. Saya akan memberikan kalian, seperti, 30 detik untuk berpikir tentang itu. 

OKE. Apakah ada yang punya menebak apa yang kasus terburuk runtime dari bubble sort adalah? Ya. 

AUDIENCE: Akan itu, seperti, n kali n minus 1 atau sesuatu seperti itu? Seperti, setiap kali berjalan, itu hanya, seperti, satu Swap kurang bahwa apa pun itu. 

ANDI PENG: Ya, jadi Anda benar-benar tepat. Dan ini adalah kasus di mana Anda Jawabannya sebenarnya lebih kompleks dari satu yang kita perlu memberikan. Jadi itu akan run-- saya akan menghapus semua ini di sini. Apakah semua orang baik? Dapatkah saya menghapus ini? OKE. Anda akan berjalan melalui n kali pertama kalinya, kan? Dan mereka akan berjalan melalui n minus 1 kedua kalinya, kan? Dan kemudian Anda akan tetap akan, n tambang 2, dan lain-lain. David melakukan ini dalam sebuah kuliah, di mana, jika Anda menambahkan semua nilai-nilai, Anda mendapatkan sesuatu yang like-- yeah lebih dari 2, yang pada dasarnya hanya mengurangi ke n kuadrat. Anda akan mendapatkan fraksi aneh di sana. Dan hanya tahu bahwa n kuadrat selalu lebih diutamakan daripada fraksi. Dan dalam hal ini, yang terburuk runtime akan n kuadrat. Jika itu di turun order, berpikir, Anda harus membuat swap setiap saat. 

Apa yang akan menjadi, berpotensi, yang terbaik kasus runtime? Katakan saja, jika daftar itu sudah dalam rangka, apa yang akan runtime itu? 

AUDIENCE: n. ANDI PENG: Ini n, persis. Dan mengapa itu n? AUDIENCE: Karena Anda hanya harus memeriksa setiap sekali. ANDI PENG: Tepat. Jadi dalam runtime terbaik, jika daftar ini sudah sorted-- katakanlah 1, 2, 3, 4-- Anda akan hanya pergi melalui, Anda akan memeriksa, Anda akan melihat, oh, mereka semua berjalan dengan baik. Saya tidak perlu menukar. Saya selesai. Jadi dalam hal ini, itu hanya n atau jumlah langkah Anda hanya harus memeriksa dalam daftar pertama. 

Dan setelah itu, kita sekarang memukul insertion sort, di mana algoritma dasarnya untuk membagi menjadi bagian diurutkan dan disortir. Dan kemudian satu per satu, nilai-nilai yang disortir dimasukkan ke dalam mereka yang sesuai posisi di awal daftar. 

Jadi misalnya, kita memiliki daftar 3, 5, 2, 6, 4 lagi. Kita tahu bahwa itu saat disortir karena kita baru saja mulai melihat itu. Kami melihat dan kita tahu bahwa nilai pertama diurutkan, kan? Jika Anda hanya melihat sebuah array ukuran satu, Anda tahu bahwa itu diurutkan. 

Jadi kita tahu bahwa empat lainnya yang tidak dipisahkan. Kami pergi melalui dan kami melihat nilai itu. Ayo kembali. Melihat bahwa nilai 5? Kami mengambil melihat itu. Kami membandingkannya dengan 3. Kita tahu bahwa itu lebih besar dari 3, jadi kita tahu bahwa yang diurutkan. Jadi sekarang kita tahu bahwa dua yang pertama diurutkan dan tiga terakhir tidak. 

Kita lihat pada 2. Kami periksa dulu dengan 5. Apakah itu kurang dari 5? Itu bukan. Jadi kita harus terus melihat ke bawah. Kemudian Anda memeriksa 2 dari 3. Apakah itu kurang dari? Tidak. Jadi Anda tahu 2 harus dimasukkan ke depan dan 3 dan 5 keduanya harus didorong keluar. Melakukan ini lagi dengan 6 dan 4. Dan kami hanya tetap memeriksa dasarnya, di mana kita hanya memeriksa, memeriksa, periksa. Dan sampai itu di kanan posisi, kita hanya jenis masukkan ke dalam posisi yang tepat, yang mana nama itu berasal. 

Jadi itu hanya algoritma, pseudocode per se, jenis, bagaimana kita akan menerapkan semacam penyisipan. Pseudo sini. Ini semua online. Jangan khawatir jika kalian mencoba untuk menyalin ini turun. Jadi sekali lagi, sama question-- apa akan menjadi yang terbaik dan terburuk runtimes untuk insertion sort? Ini sangat mirip dengan pertanyaan terakhir. Saya akan memberikan kalian, seperti, 30 detik untuk berpikir tentang ini juga. 

OK Apakah ada yang ingin memberi saya runtime terburuk? Ya. 

AUDIENCE: n kuadrat. 

ANDI PENG: Ini n kuadrat. Dan mengapa itu n kuadrat? 

AUDIENCE: Karena di urutan terbalik, Anda memiliki untuk pergi melalui n kali n, yang is-- ANDI PENG: Ya, persis. Hal sehingga sama seperti dalam semacam gelembung. Jika daftar ini di urutan, Anda akan harus memeriksa sekali pertama. Dan kemudian dengan setiap nilai tambah, Anda akan harus memeriksa terhadap setiap nilai tunggal, kan? Dan sama sekali, Anda akan membuat n lulus kali lain n lulus, yang adalah n kuadrat. Bagaimana dengan kasus terbaik? Ya. 

AUDIENCE: n minus 1, karena Yang pertama sudah kuadrat. 

ANDI PENG: Jadi, dekat. Jawabannya sebenarnya n. Karena sementara yang pertama adalah diurutkan, mungkin tidak actually-- itu kami hanya beruntung, di contoh itu, yang 2 kebetulan nomor terkecil. Tapi itu tidak akan selalu terjadi. Jika 2 sudah diurutkan di awal tetapi Anda melihat dan ada 1 di sini, 1 akan benjolan itu. Dan itu akan berakhir up yang bertemu lagian. 

Jadi dalam skenario kasus terbaik, itu sebenarnya hanya akan menjadi n. Jika Anda memiliki 1, 2, 3, 4, 5, 6, 7, 8, Anda akan dijalankan melalui bahwa seluruh daftar sekali untuk memeriksa untuk melihat apakah semuanya baik-baik saja. Apakah setiap orang yang jelas tentang berjalan kali seleksi juga? Aku tahu aku akan melalui ini benar-benar cepat. Tapi hanya tahu bahwa jika Anda tahu konsep umum, Anda harus baik. OKE. Jadi saya hanya akan memberikan kalian mungkin, seperti, satu menit untuk berbicara dengan tetangga Anda apa adalah beberapa perbedaan utama antara jenis macam. Kami akan pergi lebih dari itu segera. AUDIENCE: Oh, OK. ANDI PENG: Ya. OKE. Keren, mari kita mulai lagi sebagai kelas. OKE. Jadi ini semacam sebuah pertanyaan terbuka dalam arti bahwa ada banyak jawaban mereka. Dan kita akan membahas beberapa dari mereka sebentar. Aku hanya ingin kalian berpikir tentang apa yang dibedakan ketiga jenis macam. Dan aku mendengar, juga, besar question-- apa semacam penggabungan lakukan? Pertanyaan besar, karena itulah apa yang kita meliputi berikutnya. 

Jadi menggabungkan semacam adalah satu jenis yang berfungsi sangat berbeda dari jenis lain. Seperti kalian bisa see-- Daud melakukan demo yang di mana ia memiliki semua yang keren suara dari melihat bagaimana menggabungkan semacam berlari, seperti, jauh lebih cepat dari dua jenis lainnya? OKE. Jadi itu karena merge semacam mengimplementasikan membagi bahwa dan konsep yang kami telah menaklukkan berbicara tentang banyak dalam kuliah. Dalam arti bahwa kita ingin bekerja cerdas, bukan lebih keras, ketika Anda membagi dan menaklukkan masalah, dan istirahat mereka bawah, dan kemudian menempatkan mereka bersama-sama, hal-hal baik selalu terjadi. 

Jadi cara yang menggabungkan semacam dasarnya bekerja adalah bahwa hal itu membagi sebuah Array disortir di setengah. Dan kemudian itu punya dua bagian dari array. Dan itu hanya macam dua bagian. Itu hanya terus membagi dua, di setengah, setengah sampai semuanya diurutkan dan kemudian secara rekursif menempatkan itu semua bersama-sama. 

Jadi itu benar-benar abstrak. Jadi ini hanya sedikit pseudocode. Apakah itu masuk akal dalam cara itu berjalan? Jadi katakan saja Anda memiliki array elemen n, kan? Jika n adalah kurang dari 2, Anda dapat kembali. Karena Anda tahu bahwa jika ada hanya satu hal, itu harus dipilah. Lain, Anda menyortir kiri setengah, dan kemudian Anda menyortir bagian kanan, dan kemudian Anda bergabung. 

Jadi sementara yang terlihat benar-benar mudah, dalam kenyataannya, berpikir tentang itu agak sulit. Karena Anda seperti, baik, yang semacam berjalan pada itu sendiri. Benar? Itu berjalan dengan sendirinya. Jadi dalam hal ini, David menyentuh pada rekursi di kelas. Dan itu sebuah konsep kita akan berbicara tentang lebih. Ini yang ini, dua baris di sini, benar-benar hanya program mengatakan hal itu untuk menjalankan sendiri dengan input yang berbeda. Jadi, daripada berjalan sendiri dengan keseluruhan elemen n, Anda dapat memecahnya ke dalam setengah kiri dan kanan setengah dan kemudian jalankan lagi. 

Dan kemudian kita akan melihat secara visual, karena aku seorang pelajar visual. Ia bekerja lebih baik bagi saya. Jadi kita akan melihat contoh visual di sini. 

Katakanlah kita memiliki sebuah array, enam elemen, 3, 5, 2, 6, 4, 1, tidak diurutkan. Baiklah, ada banyak di halaman ini. Jadi jika kalian dapat melihat Langkah pertama di sini, 3, 5, 2, 6, 4, 1, Anda dapat membagi menjadi dua. Anda memiliki 3, 5, 2, 6, 4, 1. Anda tahu bahwa ini aren't-- Anda tidak tahu apakah mereka diurutkan atau tidak, sehingga Anda tetap melanggar mereka, dalam setengah, dalam setengah, setengah, sampai akhirnya, Anda hanya memiliki satu elemen. Dan salah satu unsur selalu diurutkan, kan? 

Jadi kita tahu bahwa 3, 5, 2, 4, 6, 1, dengan sendirinya, diurutkan. Dan sekarang kita bisa menempatkan mereka kembali bersama-sama. Jadi kita tahu 3, 5. Kami menempatkan mereka bersama-sama. Kita tahu itu diurutkan. 2 masih ada. Kita bisa menempatkan 4 dan 6 bersama-sama. Kita tahu bahwa yang diurutkan, sehingga kami menempatkan bersama-sama. Dan 1 ada. 

Dan kemudian Anda hanya melihat dua bagian ini di sini. Anda memiliki 3, 5, 2, 2, 3, 5. Anda hanya dapat membandingkan mulai dari segala sesuatu. Karena Anda tahu bahwa ini diurutkan dan Anda tahu bahwa yang diurutkan. Jadi Anda bahkan tidak perlu membandingkan 5, Anda hanya membandingkan 3. Dan 2 adalah kurang dari 3, sehingga Anda tahu 2 harus pergi pada akhirnya. 

Hal yang sama di sana. 1 harus pergi di sini. Dan kemudian ketika Anda pergi untuk menempatkan kedua nilai bersama-sama, Anda tahu bahwa ini diurutkan dan Anda tahu bahwa yang diurutkan. Jadi maka 1 dan 2, 1 kurang dari 2. Yang memberitahu Anda bahwa 1 harus pergi pada akhir ini bahkan tanpa melihat 3 atau 5. Dan kemudian 4, Anda bisa hanya periksa, ia pergi tepat di sini. Anda tidak harus melihat 5. Hal yang sama dengan 6. Anda tahu bahwa itu hanya 6-- tidak perlu tampak. 

Dan dengan cara itu, Anda hanya menyelamatkan diri banyak langkah-langkah ketika Anda membandingkan. Anda tidak harus membandingkan setiap unsur terhadap unsur-unsur lainnya. Anda hanya membandingkan terhadap orang-orang bahwa Anda perlu untuk membandingkannya dengan. Jadi itu semacam konsep abstrak. Jangan khawatir jika tidak cukup memukul Anda benar belum. Tapi pada umumnya, ini adalah bagaimana semacam gabungan bekerja. Pertanyaan, pertanyaan cepat, sebelum saya melanjutkan? Ya. 

AUDIENCE: Jadi Anda mengatakan bahwa Anda mengambil 1, dan kemudian 4, dan 6 dan menempatkan mereka dalam. Jadi tidak those-- tidak Anda melihat mereka sebagai elemen yang terpisah, bukan sebagai keseluruhan? ANDI PENG: Ya. Jadi apa yang terjadi adalah bahwa Anda pada dasarnya menciptakan array baru. Jadi Anda tahu bahwa, di sini, saya harus dua array ukuran 3, kan? Jadi Anda tahu bahwa array diurutkan saya perlu memiliki enam elemen. Jadi Anda hanya membuat Jumlah memory baru. Jadi Anda jenis seperti menjadi boros memori, tapi itu tidak masalah karena begitu kecil. Jadi Anda melihat 1 dan Anda melihat 2. Dan Anda tahu bahwa 1 kurang dari 2. Jadi Anda tahu bahwa 1 harus pergi di awal semua orang. 

Anda bahkan tidak perlu melihat 3 dan 5. Jadi, Anda tahu 1 pergi ke sana. Maka Anda pada dasarnya memenggal 1. Ini, seperti, mati untuk kita. Kemudian kita hanya perlu 2, 3, 5, dan kemudian 4 dan 6. Dan kemudian Anda tahu bahwa, Anda membandingkan 4 dan 2, oh, 2 harus masuk ke sana. Jadi Anda celepuk 2 bawah, Anda memotong off. Jadi Anda hanya memiliki 3 dan 5 dalam 4 dan 6. Dan Anda hanya terus memotong off sampai Anda menempatkan mereka dalam array. 

AUDIENCE: Jadi Anda hanya selalu membandingkan [tidak terdengar]? 

ANDI PENG: Tepat. Jadi dalam hal ini, Anda hanya membandingkan, pada dasarnya, satu nomor terhadap nomor lain. Dan karena Anda tahu bahwa itu diurutkan, Anda tidak harus melihat melalui semua nomor. Anda hanya perlu melihat yang pertama. Dan kemudian Anda hanya dapat celepuk mereka turun, karena Anda tahu mereka milik di mana mereka harus berada. Ya. Pertanyaan bagus. 

Dan kemudian jika salah satu dari Anda agak ambisius, merasa bebas untuk melihat kode ini. Ini sebenarnya adalah pelaksanaan fisik bagaimana kita akan menulis merge sort. Dan Anda dapat melihat, itu sangat singkat. Tapi ide dibalik itu cukup kompleks. Jadi jika Anda merasa seperti menggambar ini keluar PR malam ini Anda, jangan ragu untuk. 

OKE. Jadi David juga pergi ini di kuliah. Apa kasus terbaik runtimes, runtimes kasus terburuk, dan runtimes diharapkan dari merge semacam? Beberapa detik untuk berpikir. Ini cukup sulit, tetapi jenis intuitif jika Anda berpikir tentang hal itu. Baiklah. 

AUDIENCE: Apakah kasus terburuk n log n? ANDI PENG: Tepat. Dan mengapa itu n log n. 

AUDIENCE: Bukankah karena menjadi eksponensial lebih cepat, jadi seperti fungsi yang bukan hanya sekadar n kuadrat atau sesuatu? ANDI PENG: Tepat. Jadi alasan mengapa runtime di ini n log n adalah because-- apa yang Anda lakukan di semua langkah ini? Kau hanya memotong menjadi dua, kan? Dan jadi ketika kita sedang melakukan log, semua yang dilakukannya adalah membagi masalah di setengah, dalam setengah, setengah, lebih bagian. Dan dalam arti itu, Anda dapat jenis dari menghilangkan model linier bahwa kita telah menggunakan. Karena ketika Anda memotong hal dalam setengah, itu log. Itu hanya matematika cara untuk mewakili itu. 

Dan akhirnya, di akhir, Anda hanya membuat satu lulus lalu melalui untuk menempatkan mereka semua dalam rangka, kan? Dan jadi jika Anda hanya harus memeriksa satu hal, itu n. Dan sehingga Anda jenis mengalikan dua bersama-sama. Jadi seperti Anda punya yang akhir memeriksa n di sini dengan log n di sini. Dan jika Anda kalikan mereka, yang n log n. 

Dan kasus terbaik dan terburuk kasus dan diharapkan semua n log n. Ini juga seperti jenis lain. Ini seperti semacam seleksi dalam arti bahwa hal itu tidak peduli apa Anda daftar adalah, itu hanya akan untuk melakukan hal yang sama setiap waktu. OKE. Sehingga kalian bisa melihat, meskipun macam yang kita sudah through-- n kuadrat, itu tidak sangat efisien. Dan bahkan n log ini n adalah bukan yang paling efisien. Jika kalian ingin tahu, ada mekanisme semacam yang begitu efisien bahwa mereka hampir dasarnya datar di runtime. 

Anda punya beberapa log n. Anda punya beberapa log log n. Kami tidak menyentuh mereka di kelas ini sekarang. Tetapi jika kalian ingin tahu, merasa bebas untuk google, apa penyortiran mekanisme yang paling efisien. Saya tidak tahu, ada beberapa yang benar-benar lucu, like-- ada beberapa benar-benar yang lucu yang dilakukan orang. Dan Anda bertanya-tanya bagaimana mereka pernah memikirkan hal itu. Jadi google, jika Anda memiliki beberapa cadangan waktu, pada, apa adalah beberapa cara yang lucu yang people-- serta orang ways-- efisien telah mampu menerapkan macam. OKE. Dan di sini hanya grafik sedikit berguna. Aku tahu kalian semua, sebelum itu kuis 0, akan berada di kamar Anda mungkin mencoba menghafal itu. Jadi itu bagus di sana untuk kalian. Hanya jangan lupa logika bahwa made-- mengapa angka-angka yang terjadi. Jika Anda selalu kalah, hanya membuat Pastikan Anda tahu apa jenis yang. Dan Anda dapat menjalankan melalui mereka dalam pikiran Anda untuk mencari tahu mengapa orang-orang jawaban adalah mereka jawaban. 

Baiklah. Jadi kita akan pindah pada akhirnya, untuk pencarian. Karena orang-orang dari Anda yang telah membaca pset itu, pencarian juga merupakan bagian dari masalah minggu ini menetapkan. Anda akan diminta untuk menerapkan dua jenis pencarian. Salah satunya adalah pencarian linear dan satu adalah pencarian biner. 

Jadi pencarian linear cukup mudah. Anda hanya ingin mencari elemen dari daftar untuk melihat apakah Anda mendapatkannya. Anda hanya perlu iterate melalui. Dan jika itu sama dengan sesuatu, Anda hanya dapat kembali, kan? Tapi satu yang kita paling tertarik membicarakan adalah pencarian biner, yang benar, yang merupakan membagi dan menaklukkan mekanisme yang Daud menunjukkan dalam kuliah. 

Ingat contoh buku telepon bahwa ia terus membesarkan, salah satu yang ia jenis berjuang sedikit di tahun terakhir ini, di mana Anda membagi masalah dalam setengah, dalam setengah, setengah, lagi dan lagi, sampai Anda menemukan apa yang Anda cari? Dan Anda punya runtime dari itu juga. Dan Anda dapat melihat, itu secara signifikan lebih efisien daripada jenis lain dari pencarian. 

Jadi cara kita akan pergi tentang melaksanakan pencarian biner adalah, jika kita memiliki sebuah array, Indeks 0-6, tujuh elemen, kita dapat melihat di tengah, right-- maaf, jika pertanyaan kami first-- jika kita ingin mengajukan pertanyaan dari, apakah array mengandung unsur 7, jelas, menjadi manusia, dan memiliki seperti array kecil, mudah bagi kita untuk mengatakan ya. Tetapi cara untuk menerapkan biner pencarian akan melihat di tengah. 

Kita tahu bahwa indeks 3 adalah tengah, karena kita tahu ada tujuh elemen. Apa 7 dibagi 2? Anda dapat memotong ekstra 1. Anda punya 3 di tengah. Jadi adalah array 3 sama dengan 7? Hal ini tidak, kan? Tapi kita bisa melakukan beberapa pemeriksaan. Apakah array 3 kurang dari 7 atau adalah array 3 lebih besar dari 7? 

Dan kita tahu bahwa itu kurang dari 7. Jadi kita tahu bahwa, oh, itu harus tidak berada di kiri setengah. Kita tahu bahwa hal itu harus di bagian kanan, kan? Jadi kami hanya bisa memenggal setengah array. Kami bahkan tidak perlu melihat lagi. Karena kita tahu bahwa setengah dari problem-- kami kita tahu bahwa jawabannya adalah di kanan setengah dari masalah kita. Jadi kita hanya melihat itu sekarang. 

Jadi sekarang kita melihat tengah apa yang tersisa. Indeks yang 5. Kami melakukan cek sama lagi dan kita melihat bahwa itu lebih kecil. Jadi kita melihat di sebelah kiri itu. Dan kemudian kita melihat bahwa cek. Apakah nilai array di Indeks 4 sama dengan 7? Ini. Jadi kita bisa kembali benar, karena kami menemukan nilai dalam daftar kami. Apakah cara saya pergi melalui yang masuk akal untuk semua orang? OKE. Saya akan memberikan kalian mungkin, seperti, tiga, empat menit untuk mencari tahu bagaimana pseudocode ini di. 

Jadi bayangkan saya meminta Anda untuk menulis fungsi yang disebut pencarian () yang kembali nilai, nilai Boolean, itu benar atau false-- seperti, benar jika Anda menemukan nilai, false jika Anda tidak. Dan kemudian Anda disahkan pada nilai Anda sedang mencari ke dalam nilai-nilai, yang adalah array-- oh, saya pasti menempatkan bahwa di tempat yang salah. OKE. Anyways, yang harus memiliki pernah ke kanan nilai. Dan kemudian int n adalah nomor elemen dalam array itu. Bagaimana Anda pergi tentang mencoba untuk pseudocode bahwa masalah di? Saya akan memberikan orang-orang seperti tiga menit untuk melakukan itu. Tidak, saya pikir ada only-- yeah, ada satu yang tepat di sini. AUDIENCE: Dapatkah saya? ANDI PENG: Ya, saya punya Anda. Apakah kerja itu? OK keren. 

OKE. Semua orang yang tepat, kita akan mengekang dalam. OKE. Jadi asumsikan kita punya ini indah sedikit array dengan nilai n di dalamnya. Aku tidak menggambar garis. Tapi bagaimana kita akan pergi tentang mencoba untuk menulis ini? Apakah ada yang ingin memberikan baris pertama? Jika Anda ingin memberi saya baris pertama dari pseudocode ini. 

AUDIENCE: [tidak terdengar] AUDIENCE: Anda ingin iterate through-- AUDIENCE: Just another untuk loop? AUDIENCE: --Untuk. 

ANDI PENG: Jadi yang satu ini agak sulit. Pikirkan about-- Anda ingin terus berjalan lingkaran ini berulang-ulang sampai kapan? 

AUDIENCE: Sampai [tidak terdengar] nilai sama dengan nilai tersebut. ANDI PENG: Tepat. Jadi Anda benar-benar bisa hanya write-- kita bahkan dapat menyederhanakan lebih. Kami hanya bisa melakukan loop sementara, kan? Jadi Anda hanya dapat memiliki loop-- kita tahu bahwa itu sementara. Tapi untuk sekarang, aku akan mengatakan "loop" - melalui apa? Lingkaran until-- apa kondisi kita berakhir? Saya pikir saya mendengar itu. Aku mendengar seseorang mengatakan itu. 

AUDIENCE: Nilai sama tengah. ANDI PENG: Katakan lagi. AUDIENCE: Atau, sampai Nilai yang Anda cari adalah sama dengan nilai tengah. 

ANDI PENG: Bagaimana jika itu tidak di sana? Bagaimana jika nilai yang Anda cari adalah tidak benar-benar dalam array ini? AUDIENCE: Anda kembali 1. 

ANDI PENG: Tapi apa yang kita ingin loop sampai jika kita memiliki kondisi? Ya. 

AUDIENCE: Sampai hanya ada satu nilai? ANDI PENG: Anda dapat loop until-- sehingga Anda tahu bahwa Anda akan memiliki nilai max, kan? Dan Anda tahu bahwa Anda akan memiliki nilai min, kan? Karena juga, itu sesuatu Aku lupa mengatakan sebelumnya, bahwa sesuatu yang kritis tentang pencarian biner adalah bahwa array Anda sudah diurutkan. Karena tidak ada cara untuk melakukan ini jika mereka nilai hanya acak. Anda tidak tahu jika salah satu yang lebih besar dari yang lain, kan? 

Jadi, Anda tahu bahwa Anda dan max menit Anda di sini, kan? Jika Anda akan menyesuaikan maks Anda di menit Anda dan mid-- mari kita hanya berasumsi Anda Nilai pertengahan adalah di sini-benar Anda akan dasarnya lingkaran sampai minimum Anda hampir sama dengan max Anda, kanan, atau jika max Anda tidak sama dengan min Anda. Benar? Karena ketika itu terjadi, Anda tahu bahwa Anda telah akhirnya memukul nilai yang sama. Jadi Anda ingin loop sampai menit Anda kurang dari atau sama to-- oops, tidak kurang dari atau sama dengan, cara lain around-- max adalah. 

Apakah itu masuk akal? Aku mengambil beberapa mencoba untuk mendapatkan hak itu. Tapi loop sampai nilai maks Anda pada dasarnya hampir kurang dari atau sama dengan minimum Anda, kan? Saat itulah Anda tahu bahwa Anda telah berkumpul. AUDIENCE: Ketika akan maksimum nilai kurang dari minimum? ANDI PENG: Jika Anda terus menyesuaikan itu, yang adalah apa yang kita akan akan melakukan dalam hal ini. Apakah itu masuk akal? Minimum dan maksimum hanya bilangan bulat bahwa kita mungkin akan ingin membuat tetap melacak di mana kita cari. Karena array ada terlepas dari apa yang kita lakukan. Seperti, kita tidak benar-benar secara fisik memenggal array, kan? Kami hanya menyesuaikan di mana kita cari. Apakah itu masuk akal? 

AUDIENCE: Ya. 

ANDI PENG: OK. Jadi kalau itu kondisi untuk loop kami, apa yang kita inginkan dalam lingkaran ini? Apa yang kita akan ingin lakukan? Jadi sekarang, kita punya maks dan min, tepat, mungkin dibuat di sini di suatu tempat. Kita akan mungkin ingin untuk menemukan tengah, kanan? Bagaimana kita akan menjadi dapat menemukan tengah? Apa yang mathematical-- AUDIENCE: Max ditambah min dibagi 2. ANDI PENG: Tepat. Apakah itu masuk akal? Dan kalian melihat mengapa kami tidak hanya use-- mengapa kita melakukan ini bukannya melakukan hanya n dibagi 2? Itu karena n adalah nilai itu akan tetap sama. Benar? Tapi seperti yang kita menyesuaikan minimum dan nilai maksimum, mereka akan berubah. Dan sebagai hasilnya, kami tengah akan berubah juga. Jadi itu sebabnya kami ingin melakukan ini dengan benar di sini. OKE. 

Dan kemudian, sekarang kami telah menemukan our-- ya. 

AUDIENCE: Hanya question-- cepat ketika Anda mengatakan min dan max, kita mengasumsikan bahwa itu sudah diurutkan? 

ANDI PENG: Ya, itu benar-benar prasyarat untuk pencarian biner, bahwa Anda harus tahu itu diurutkan. Itulah sebabnya semacam, Anda menulis di Anda Masalah ditetapkan sebelum pencarian biner Anda. OKE. Jadi sekarang kita tahu di mana titik tengah kami adalah, apa yang Anda ingin lakukan di sini? 

AUDIENCE: Kami ingin membandingkan bahwa untuk yang lain. ANDI PENG: Tepat. Jadi Anda akan membandingkan pertengahan hingga nilai, kan? Dan apa yang memberitahu kita ketika kita membandingkan? Apa yang ingin kita lakukan setelah itu? 

AUDIENCE: Jika nilai lebih besar dari pertengahan, kita ingin memotongnya. ANDI PENG: Tepat. Jadi jika nilai lebih besar dari pertengahan, kami akan ingin mengubah ini minimum dan Maxes, kan? Apa yang kita ingin berubah? Jadi jika kita tahu nilai adalah suatu tempat di sini, apa yang Anda kita berubah? Kami ingin mengubah kami minimum menjadi pertengahan, kan? Dan kemudian yang lain, jika dalam ini setengah, apa yang kita ingin berubah? 

AUDIENCE: maksimum Anda. ANDI PENG: Ya. Dan kemudian Anda hanya akan untuk menjaga perulangan, kan? Karena sekarang, setelah satu iterasi melalui, Anda punya max di sini. Dan kemudian Anda dapat menghitung ulang pertengahan. Dan kemudian Anda dapat membandingkan. Dan Anda akan terus sampai menit dan Maxes telah dasarnya berkumpul. Dan saat itulah Anda tahu bahwa Anda telah memukul akhir itu. Dan baik Anda telah menemukan itu atau Anda belum pada saat itu. 

Apakah ini masuk akal untuk semua orang? OKE. Ini sangat penting, karena Anda akan memiliki untuk menulis ini dalam kode malam Anda. Tapi kalian memiliki cukup bagus rasa apa yang seharusnya Anda lakukan, yang mana yang bagus. OKE. Jadi kita punya sekitar tujuh menit tersisa bagian. Jadi kita akan berbicara tentang pset ini yang akan kita lakukan. Jadi pset dibagi menjadi dua bagian. Babak pertama melibatkan menerapkan find di mana Anda menulis pencarian linear, sebuah pencarian biner, dan algoritma sorting. 

Jadi ini adalah pertama waktu di mana pset kami akan memberikan kalian apa yang disebut kode distribusi, yang merupakan kode bahwa kita telah pra-ditulis, tetapi hanya meninggalkan beberapa potongan off bagi Anda untuk menyelesaikan menulis. Jadi kalian, ketika Anda melihat ini kode, Anda mungkin akan benar-benar takut. Jika Anda hanya suka, ahh, aku tidak tahu apa yang dilakukan, Saya tidak tahu, seperti, yang tampaknya begitu rumit, ahh, bersantai. Tidak apa-apa. Baca spec. Spec akan menjelaskan kepada Anda persis apa semua program ini lakukan. 

Misalnya, generate.c adalah sebuah program yang akan datang dengan pset Anda. Anda tidak benar-benar harus menyentuhnya, tapi Anda harus memahami apa yang dilakukannya. Dan generate.c, semua itu lakukan adalah baik menghasilkan angka acak atau Anda dapat memberikan benih, seperti Jumlah diatur sebelumnya bahwa dibutuhkan, dan menghasilkan angka lebih. Jadi ada cara khusus untuk menerapkan generate.c di mana Anda hanya dapat membuat sekelompok angka bagi Anda untuk menguji metode Anda yang lain pada. 

Jadi jika Anda ingin, untuk Misalnya, menguji menemukan Anda, Anda akan ingin menjalankan generate.c, menghasilkan sekelompok angka, dan kemudian menjalankan fungsi pembantu Anda. Fungsi pembantu Anda adalah di mana Anda sebenarnya secara fisik menulis kode. Dan memikirkan pembantu sebagai file library Anda menulis menemukan yang menelepon. Dan dalam helpers.c, Anda akan melakukan pencarian dan menyortir. 

Dan kemudian Anda akan dasarnya hanya menempatkan mereka semua bersama-sama. Spec akan memberitahu Anda bagaimana untuk menempatkan bahwa pada baris perintah. Dan Anda akan dapat menguji apakah tidak semacam Anda dan pencari kerja. Keren. Apakah ada yang sudah dimulai dan masalah yang dihadapi atau pertanyaan mereka miliki sekarang dengan ini? OKE. 

AUDIENCE: Tunggu. Saya punya pertanyaan. 

ANDI PENG: Ya. 

AUDIENCE: Jadi saya mulai melakukan pencarian linear di helpers.c dan itu tidak benar-benar bekerja. Tapi kemudian, saya menemukan kami hanya harus menghapusnya dan melakukan pencarian biner. Jadi tidak masalah jika tidak bekerja? 

ANDI PENG: Jawaban singkat adalah tidak. Tapi karena kami not-- AUDIENCE: Tapi ada satu benar-benar memeriksa. ANDI PENG: Kami tidak pernah akan melihat itu. Tapi Anda mungkin ingin membuat yakin pencarian Anda bekerja. Karena jika Anda linear pencarian tidak bekerja, maka kemungkinan biner Anda pencarian tidak akan bekerja dengan baik. Karena Anda memiliki yang sama logika dalam keduanya. Dan tidak, itu tidak terlalu penting. Jadi satu-satunya Anda akan berubah di adalah semacam dan pencarian biner. Ya. 

Dan juga, banyak anak-anak yang mencoba untuk mengkompilasi helpers.c. Anda tidak benar-benar diperbolehkan untuk melakukan itu, karena helpers.c tidak memiliki fungsi utama. Dan sehingga Anda hanya harus akan benar-benar kompilasi menghasilkan dan menemukan, karena menemukan panggilan helpers.c dan fungsi di dalamnya. Sehingga membuat debugging rasa sakit di pantat. Tapi itulah yang harus kita lakukan. AUDIENCE: Anda hanya membuat semua, kan? ANDI PENG: Anda hanya dapat membuat semua juga, ya. OKE. Jadi itu dalam hal apa pset yang meminta Anda semua untuk melakukan. Jika Anda memiliki pertanyaan, merasa bebas untuk bertanya kepada saya setelah bagian. Saya akan berada di sini untuk, seperti, 20 menit. 

Dan yeah, pset ini benar-benar tidak buruk. Kalian harus OK. Ini, hanya mengikuti pedoman. Jenis memiliki rasa, secara logis, apa harus terjadi dan Anda akan baik-baik saja. Jangan terlalu takut. Ada banyak kode sudah tertulis di sana. Jangan terlalu takut jika Anda tidak mengerti apa semua itu berarti. Jika itu banyak, itu benar-benar baik-baik saja. Dan datang ke kantor jam. Kami akan membantu anda melihat. 

AUDIENCE: Dengan tambahan fungsi, kita melihat orang-up? 

ANDI PENG: Ya, mereka adalah dalam kode. Dalam permainan 15, setengah dari itu sudah ditulis untuk Anda. Jadi fungsi-fungsi yang sudah dalam kode. Yep. Baiklah. Nah, terbaik keberuntungan. Ini hari menjijikkan. Jadi mudah-mudahan kalian tidak merasa terlalu buruk tentang tinggal di dalam dan coding.