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.