>> [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]