>> [MUZIK Bermain]
>> ZAMYLA CHAN: Perkara pertama yang anda mungkin notis mengenai find ialah kita sudah
telah kod bertulis untuk kita.
Ini dipanggil kod pengedaran.
Oleh itu, kita tidak hanya menulis kita sendiri kod dari awal lagi.
Sebaliknya, kami mengisi lompang dalam beberapa kod yang sedia ada.
>> Program find.c menggesa untuk nombor untuk mengisi sisa rumput kering itu, mencari yang
sisa rumput kering jarum pengguna dikemukakan, dan ia melakukan ini dengan memanggil menyusun dan
carian, fungsi yang ditakrif dalam helpers.c.
Jadi find.c ditulis sudah.
Tugas anda adalah untuk menulis pembantu.
>> Jadi apa yang kita lakukan?
Kami melaksanakan dua fungsi.
Cari, yang mengembalikan benar jika nilai terdapat dalam sisa rumput kering, kembali
palsu jika nilai adalah tidak dalam sisa rumput kering itu.
Dan maka kita juga melaksanakan jenis yang mengisih tatasusunan dipanggil nilai-nilai.
>> Jadi mari kita menangani carian.
Cari kini dilaksanakan sebagai carian linear, tetapi anda boleh melakukan banyak
lebih baik daripada itu.
Carian Linear dilaksanakan di O n masa, yang agak perlahan.
Walaupun, ia boleh mencari mana-mana senarai yang diberikan kepadanya.
Tugas anda adalah untuk melaksanakan carian binari, yang telah menjalankan masa O log n.
Itu agak cepat.
>> Tetapi ada ketetapan yang.
Carian binari hanya boleh mencari melalui senarai pra-disusun.
Mengapa?
>> Nah mari kita lihat satu contoh.
Memandangkan pelbagai nilai, sisa rumput kering itu, kita akan mencari
untuk jarum.
Dan dalam contoh ini, integer tiga.
Cara bahawa carian binari berfungsi ialah kita bandingkan nilai pertengahan
array untuk jarum, sama seperti bagaimana kami membuka buku telefon ke tengah
halaman pada minggu sifar.
>> Jadi selepas membandingkan nilai tengah untuk jarum, anda boleh membuang sama ada
kiri atau separuh betul array dengan mengetatkan batas anda.
Dalam kes ini, sejak tiga, jarum kita, adalah kurang daripada 10, nilai menengah,
betul terikat boleh berkurangan.
Tetapi cuba untuk membuat batas anda sebagai ketat yang mungkin.
Jika nilai tengah bukan jarum, maka anda tahu bahawa anda tidak perlu
termasuk dalam carian anda.
Jadi anda betul terikat boleh mengetatkan batas carian hanya sedikit kecil lebih,
dan sebagainya dan sebagainya sehingga anda mencari jarum anda.
>> Jadi apakah kod pseudo yang kelihatan seperti?
Nah sementara kita masih mencari melalui senarai dan masih mempunyai elemen untuk
melihat, kami mengambil pertengahan senarai, dan bandingkan bahawa nilai menengah untuk
jarum kami.
Jika mereka sama, maka ini bermakna kita telah didapati jarum dan kita boleh
kembali benar.
>> Jika tidak, jika jarum adalah kurang daripada nilai tengah, maka itu bermakna kita
boleh membuang separuh yang betul, dan hanya mencari sebelah kiri array.
Jika tidak, kami akan mencari kanan array.
Dan pada akhirnya, jika anda tidak mempunyai apa-apa lebih banyak unsur kiri untuk mencari tetapi anda
tidak menemui jarum anda lagi, maka anda pulangan palsu kerana jarum
pasti tidak dalam sisa rumput kering itu.
>> Sekarang satu perkara yang kemas mengenai kod pseudo ini dalam carian binari adalah bahawa ia boleh menjadi
ditafsirkan sebagai sama ada lelaran atau pelaksanaan rekursif.
Jadi ia akan menjadi rekursif jika anda dipanggil fungsi carian dalam carian
berfungsi pada sama ada separuh daripada array.
Kami akan meliputi rekursi sedikit kemudian di Sudah tentu, tetapi tahu bahawa ia adalah satu
pilihan jika anda ingin mencuba.
>> Sekarang mari kita lihat jenis.
Disusun mengambil pelbagai dan integer n, yang merupakan saiz array.
Sekarang terdapat pelbagai jenis pelbagai, dan anda boleh lihat beberapa
seluar pendek untuk demo dan penerangan.
Jenis balasan kami fungsi jenis adalah tidak sah.
Ini bermakna bahawa kita tidak akan untuk mengembalikan mana-mana pelbagai dari jenis.
Kami benar-benar akan menukar sangat array yang telah diluluskan ke dalam kita.
>> Dan itu mungkin kerana tatasusunan adalah diluluskan dengan merujuk dalam C. Sekarang kita akan
melihat lebih lanjut mengenai ini kemudian, tetapi Perbezaan penting antara yang berlalu
dalam sesuatu seperti integer dan lulus dalam array, ialah apabila anda
lulus dalam integer, C hanya akan membuat salinan integer itu dan lulus
kepada majlis itu.
Pembolehubah asal tidak akan berubah sekali fungsi selesai.
Dengan array, di sisi lain, ia tidak akan membuat salinan, dan anda akan
sebenarnya menyunting sangat pelbagai sendiri.
>> Jadi satu jenis jenis adalah jenis pilihan.
Jenis pilihan berfungsi dengan bermula mulanya, dan kemudian anda melelar
lebih dan mencari elemen yang paling kecil.
Dan kemudian anda swap yang paling kecil elemen dengan yang pertama.
Dan kemudian anda bergerak ke elemen kedua , Cari yang paling kecil seterusnya
unsur, dan kemudian menukar bahawa dengan Elemen kedua dalam tatasusunan kerana
elemen pertama telah disusun.
Dan demikian maka anda terus untuk setiap unsur dalam mengenal pasti yang paling kecil
nilai dan bertukar-tukar ia keluar.
>> Aku sama dengan 0, elemen yang pertama n tolak 1, anda akan membandingkan
setiap nilai akan datang selepas itu dan mendapati indeks nilai minimum.
Sebaik sahaja anda mencari indeks nilai minimum, anda boleh menukar bahawa nilai array
minimum dan mudah I.
>> Satu lagi jenis jenis yang anda boleh melaksanakan adalah jenis gelembung.
Jadi iterates isih gelembung ke senarai membandingkan unsur yang bersebelahan dan
bertukar-tukar unsur-unsur yang adalah dalam perintah itu salah.
Dan cara ini, unsur terbesar akan gelembung ke akhir.
Dan senarai itu disusun sekali tidak lebih elemen telah ditukar.
>> Jadi mereka adalah dua contoh jenis algoritma yang anda boleh melaksanakan untuk
program find.
Sebaik sahaja anda selesai jenis, dan anda telah carian dilakukan, anda selesai.
Nama saya Zamyla, dan ini adalah CS50.
>> [MUZIK Bermain]