>> 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 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 hal ini Sebagai contoh, integer 3.
>> Cara bahawa carian binari berfungsi ialah kita bandingkan nilai pertengahan
array untuk jarum, sama seperti bagaimana kami telah membuka buku telefon ke tengah
halaman dalam Minggu 0.
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 3, jarum kita, 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 hak anda terikat boleh mengetatkan batas carian hanya sedikit kecil lebih,
dan sebagainya dan seterusnya, sehingga anda mencari jarum anda.
>> Jadi apa yang tidak pseudo kod kelihatan seperti?
Nah, sementara kita masih mencari melalui senarai dan masih mempunyai
unsur-unsur untuk mencari, kami mengambil tengah-tengah senarai dan bandingkan yang
nilai sederhana kepada 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 bukan dalam sisa rumput kering itu.
>> Sekarang, satu perkara yang kemas mengenai pseudo ini kod dalam carian binari adalah bahawa ia boleh
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 dalam kursus ini.
Tetapi tahu bahawa ia merupakan satu pilihan jika anda ingin mencuba.