>> ZAMYLA จัน: สิ่งแรกที่คุณอาจ แจ้งให้ทราบเกี่ยวกับการค้นพบก็คือว่าเราอยู่แล้ว
มีโค้ดที่เขียนสำหรับเรา
นี้เรียกว่ารหัสการกระจาย
ดังนั้นเราไม่ได้เพียงแค่เขียนของเราเอง รหัสจากรอยขีดข่วนอีกต่อไป
แต่เรากำลังการกรอกในช่องว่าง ในบางรหัสที่มีอยู่แล้ว
>> โปรแกรม find.c แจ้งให้สำหรับหมายเลข เพื่อเติมกองหญ้า, การค้นหา
กองหญ้าสำหรับเข็มที่ใช้ส่ง และมันไม่นี้โดยการโทรและการจัดเรียง
ฟังก์ชั่นการค้นหาที่กำหนดไว้ ใน helpers.c
ดังนั้น find.c ถูกเขียนอยู่แล้ว
งานของคุณคือการเขียนผู้ช่วยเหลือ
>> ดังนั้นสิ่งที่เรากำลังทำอะไร
เรากำลังดำเนินการทั้งสองฟังก์ชั่น
ค้นหาซึ่งผลตอบแทนจริงถ้าค่า ที่พบในกองหญ้ากลับ
เท็จถ้าค่าเป็น ไม่ได้อยู่ในกองหญ้า
แล้วเรายังมีการดำเนินการเรียงลำดับ ซึ่งเรียงลำดับแถวที่เรียกว่าค่า
เพื่อให้ต่อสู้ของการค้นหา
>> การค้นหาจะดำเนินการในปัจจุบัน เช่นค้นหาเชิงเส้น
แต่คุณสามารถทำดีกว่าที่
ค้นหาเชิงเส้นจะดำเนินการใน O ของ n เวลาที่ช้ามากแม้ว่ามันจะ
สามารถค้นหารายการใด ๆ ที่กำหนดให้
งานของคุณคือการใช้การค้นหาแบบไบนารี ซึ่งได้ใช้เวลา O ของบันทึก n
นั่นคืออย่างรวดเร็ว
>> แต่มีข้อตกลง
ค้นหาแบบไบนารีสามารถค้นหา ผ่านรายการที่เรียงลำดับก่อน
ทำไมจึงเป็นเช่นนั้น
ดีขอดูตัวอย่าง
ป.ร. ให้ไว้ ณ อาร์เรย์ของค่า, กองหญ้าที่ เรากำลังจะมองหา
เข็มและในนี้ เช่นเลขที่ 3
>> วิธีการที่ค้นหาแบบไบนารีทำงานคือ เราเปรียบเทียบค่ากลางของ
อาร์เรย์ที่เข็มเหมือนวิธี เราเปิดสมุดโทรศัพท์กลาง
หน้าในสัปดาห์ที่ 0
ดังนั้นหลังจากการเปรียบเทียบค่ากลาง เข็มคุณสามารถทิ้งอย่างใดอย่างหนึ่ง
ด้านซ้ายหรือด้านขวาของอาร์เรย์ โดยกระชับขอบเขตของคุณ
ในกรณีนี้ตั้งแต่ 3 เข็มของเราเป็น น้อยกว่า 10 ค่ากลาง
ผูกพันที่เหมาะสมสามารถลด
>> แต่พยายามที่จะทำให้ขอบเขตของคุณ แน่นที่สุดเท่าที่ทำได้
ถ้าค่าตรงกลางไม่ได้เป็นเข็ม แล้วคุณจะรู้ว่าคุณไม่จำเป็นต้อง
รวมไว้ในการค้นหาของคุณ
ดังนั้นตอนของคุณผูกพันสามารถกระชับ ขอบเขตการค้นหาเพียงเล็กน้อยมากขึ้น
และอื่น ๆ และอื่น ๆ จน คุณพบว่าเข็มของคุณ
>> ดังนั้นสิ่งที่จะหลอก รหัสมีลักษณะอย่างไร
ดีในขณะที่เรายังคงมองผ่าน รายการและยังคงมี
องค์ประกอบที่จะมองไปในเราจะอยู่ตรงกลาง ของรายการและเปรียบเทียบว่า
ค่ากลางเข็มของเรา
หากพวกเขากำลังเท่ากันแล้วนั่นหมายความว่าเราได้ พบเข็มและที่เราสามารถทำได้
กลับจริง
>> มิฉะนั้นถ้าเข็มน้อยกว่า ค่ากลางแล้วนั่นหมายความว่าเรา
สามารถทิ้งครึ่งหนึ่งที่เหมาะสมและเพียงแค่ ค้นหาที่ด้านซ้ายของแถว
มิฉะนั้นเราจะค้นหา ด้านขวาของอาร์เรย์
และในท้ายที่สุดถ้าคุณไม่ได้มี องค์ประกอบอื่น ๆ ที่เหลือในการค้นหา แต่คุณ
ยังไม่พบเ​​ข็มของคุณยัง แล้วคุณกลับเท็จ
เพราะเข็มที่แน่นอน ไม่ได้อยู่ในกองหญ้า
>> ตอนนี้สิ่งหนึ่งที่ระเบียบเกี่ยวกับการหลอกนี้ ในการค้นหารหัสเลขฐานสองก็คือว่ามันสามารถ
ถูกตีความว่าเป็นอย่างใดอย่างหนึ่งซ้ำแล้วซ้ำอีก หรือการดำเนินการซ้ำ
ดังนั้นมันจะซ้ำถ้าคุณเรียกว่า ฟังก์ชันการค้นหาในการค้นหา
ฟังก์ชั่นในครึ่งหนึ่งของอาร์เรย์ทั้ง
เราจะครอบคลุมการเรียกซ้ำบิต ต่อมาในหลักสูตร
แต่รู้ว่ามันเป็นตัวเลือกที่ ถ้าคุณต้องการที่จะลอง