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. 

Cari dilaksanakan saat ini sebagai pencarian linear. Tapi Anda bisa melakukan jauh lebih baik dari itu. Pencarian linear diimplementasikan dalam O n waktu, yang cukup lambat, meskipun dapat mencari daftar yang diberikan untuk itu. 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 hal ini Misalnya, integer 3. 

Cara bahwa pencarian biner bekerja adalah bahwa kita membandingkan nilai tengah array ke jarum, seperti bagaimana kami membuka buku telepon ke tengah Halaman dalam Minggu 0. Jadi setelah membandingkan nilai tengah untuk jarum, Anda dapat membuang baik kiri atau kanan setengah dari array dengan memperketat batas Anda. Dalam hal ini, sejak 3, jarum kita, 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 Anda benar terikat dapat mengencangkan batas pencarian hanya sedikit lebih, dan seterusnya dan sebagainya, sampai Anda menemukan jarum Anda. 

Jadi, apa pseudo Kode terlihat seperti? Nah, sementara kita masih mencari melalui daftar dan masih memiliki elemen untuk melihat ke dalam, 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 bisa membuang setengah benar dan adil 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 kembali palsu. Karena jarum pasti tidak di tumpukan jerami. 

Sekarang, satu hal yang rapi tentang semu ini kode 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 dalam kursus. Tapi jangan tahu bahwa itu adalah pilihan jika Anda ingin mencoba.