[MUSIC PLAYING] 

ZAMYLA CHAN: Hal pertama yang Anda mungkin pemberitahuan tentang menemukan adalah bahwa kita sudah memiliki kode ditulis untuk kita. Ini disebut kode distribusi. Jadi kita tidak hanya menulis kita sendiri kode dari awal lagi. Sebaliknya, kita mengisi rongga dalam beberapa kode yang sudah ada. 

Program find.c meminta untuk nomor untuk mengisi tumpukan jerami, akan mencari tumpukan jerami untuk jarum pengguna disampaikan, dan hal ini dengan memanggil mengurutkan dan pencarian, fungsi didefinisikan di helpers.c. Jadi find.c ditulis sudah. Tugas Anda adalah menulis pembantu. 

Jadi apa yang kita lakukan? Kami melaksanakan dua fungsi. Search, yang mengembalikan true jika nilai ditemukan dalam tumpukan jerami, kembali false jika nilai adalah bukan di tumpukan jerami. Dan kemudian kita juga menerapkan semacam yang macam array yang disebut nilai-nilai. 

Jadi mari kita menangani pencarian. Pencarian saat ini diimplementasikan sebagai pencarian linear, tetapi Anda dapat melakukan banyak lebih baik dari itu. Pencarian linear diimplementasikan dalam O waktu n, yang cukup lambat. Meskipun, dapat mencari setiap daftar yang diberikan kepadanya. Tugas Anda adalah untuk melaksanakan pencarian biner, yang telah berjalan waktu O dari log n. Itu cukup cepat. 

Tapi ada ketentuan a. Pencarian biner hanya dapat mencari melalui daftar pra-diurutkan. Mengapa demikian? 

Nah mari kita lihat sebuah contoh. Mengingat sebuah array nilai, tumpukan jerami, kita akan melihat untuk jarum. Dan dalam contoh ini, integer tiga. Cara bahwa pencarian biner bekerja adalah bahwa kita membandingkan nilai tengah array ke jarum, seperti bagaimana kami membuka buku telepon ke tengah Halaman dalam seminggu nol. 

Jadi setelah membandingkan nilai tengah untuk jarum, Anda dapat membuang baik kiri atau kanan setengah dari array dengan memperketat batas Anda. Dalam kasus ini, sejak tiga, jarum kami, kurang dari 10, nilai tengah, benar terikat dapat menurunkan. Tapi cobalah untuk membuat batas Anda seketat mungkin. Jika nilai tengah tidak jarum, maka Anda tahu bahwa Anda tidak perlu memasukkannya dalam pencarian Anda. Jadi kau benar terikat dapat mengencangkan batas pencarian hanya sedikit lebih, dan seterusnya dan seterusnya sampai Anda menemukan jarum Anda. 

Jadi apa pseudocode terlihat seperti? Nah sementara kita masih melihat melalui daftar dan masih memiliki elemen untuk melihat, kita mengambil tengah daftar, dan membandingkan nilai tengah untuk jarum kami. Jika mereka sama, maka itu berarti kita sudah menemukan jarum dan kita bisa kembali benar. 

Jika tidak, jika jarum kurang dari nilai tengah, maka itu berarti kita dapat membuang bagian kanan, dan hanya mencari sisi kiri array. Jika tidak, kami akan mencari sisi kanan dari array. Dan pada akhirnya, jika Anda tidak memiliki lebih elemen yang tersisa untuk mencari tapi Anda belum menemukan jarum Anda belum, maka Anda return false karena jarum pasti tidak di tumpukan jerami. 

Sekarang hal yang rapi tentang pseudocode ini dalam pencarian biner adalah bahwa hal itu dapat diartikan baik sebagai berulang atau implementasi rekursif. Jadi akan rekursif jika Anda menelepon fungsi pencarian dalam pencarian berfungsi di kedua setengah dari array. Kita akan membahas rekursi sedikit kemudian di tentu saja, tapi tahu bahwa itu adalah pilihan jika Anda ingin mencoba. 

Sekarang mari kita lihat semacam. Urutkan mengambil array dan integer n, yang merupakan ukuran array. Sekarang ada berbagai jenis macam, dan Anda dapat melihat beberapa celana pendek untuk demo dan penjelasan. Jenis kembali untuk kami Fungsi semacam ini batal. Jadi itu berarti bahwa kita tidak akan untuk kembali Array apapun dari macam. Kami benar-benar akan mengubah sangat array itu disahkan ke dalam diri kita. 

Dan itu mungkin karena array dikirimkan dengan referensi di C. Sekarang kita akan lihat lebih lanjut tentang ini nanti, tetapi perbedaan penting antara passing dalam sesuatu seperti integer dan passing dalam array, adalah bahwa ketika Anda lulus dalam integer, C hanya akan membuat salinan dari integer yang dan lulus ke fungsi. Variabel asli tidak akan berubah setelah fungsi ini selesai. Dengan sebuah array, di sisi lain, itu tidak akan membuat salinan, dan Anda akan sebenarnya bisa mengedit sangat array itu sendiri. 

Jadi satu jenis semacam ini semacam seleksi. The selection sort bekerja dengan mulai awal, dan kemudian Anda iterate atas dan menemukan elemen terkecil. Dan kemudian Anda swap yang terkecil elemen dengan yang pertama. Dan kemudian Anda pindah ke elemen kedua , Menemukan terkecil berikutnya elemen, dan kemudian swap bahwa dengan elemen kedua dalam array karena elemen pertama sudah diurutkan. Dan kemudian Anda melanjutkan untuk setiap elemen dalam mengidentifikasi terkecil nilai dan swapping keluar. 

Karena aku sama dengan 0, elemen pertama untuk n dikurangi 1, Anda akan membandingkan setiap nilai berikutnya setelah itu dan menemukan indeks dari nilai minimum. Setelah Anda menemukan indeks nilai minimum, Anda dapat swap bahwa nilai array minimum dan berbagai I. 

Tipe lain dari jenis yang dapat Anda menerapkan adalah bubble sort. Jadi bubble sort iterates atas daftar membandingkan elemen yang berdekatan dan swapping elemen yang berada dalam urutan yang salah. Dan cara ini, elemen terbesar akan gelembung sampai akhir. Dan daftar ini diurutkan sekali tidak lebih unsur telah bertukar. 

Jadi mereka adalah dua contoh semacam algoritma yang dapat Anda menerapkan untuk program find. Setelah Anda selesai menyortir, dan Anda sudah dilakukan pencarian, Anda sudah selesai. Nama saya adalah Zamyla, dan ini adalah CS50. 

[MUSIC PLAYING]