>> ROB สลิง: สวัสดีครับผมร็อบ
เราจะใช้ค้นหาแบบไบนารีได้อย่างไร
ลองหา
ดังนั้นโปรดทราบว่าการค้นหานี้เรากำลังจะ ในการดำเนินการซ้ำ
นอกจากนี้คุณยังสามารถใช้ค้นหาแบบไบนารี ซ้ำดังนั้นหากคุณไม่ว่า
ที่ดีอย่างสมบูรณ์แบบ
>> ตอนแรกให้จำสิ่งที่ พารามิเตอร์เพื่อค้นหาจะหมายถึงการเป็น
ที่นี่เราเห็นคุณค่า int ซึ่งเป็น ควรจะเป็นค่าผู้ใช้
ค้นหา
เราจะเห็นอาร์เรย์ค่า int ซึ่ง เป็นอาร์เรย์ที่เรากำลัง
หาค่า
และเราจะเห็น int n ซึ่งคือ ความยาวของอาร์เรย์ของเรา
>> ตอนนี้สิ่งแรกที่แรก
เราตรวจสอบเพื่อดูว่า n เท่ากับ 0 ใน ซึ่งในกรณีที่เรากลับเท็จ
นั่นคือคำพูดว่าถ้าเรามีที่ว่าง อาร์เรย์ค่าเป็นอย่างชัดเจนไม่ได้อยู่ใน
แถวที่ว่างเปล่าเพื่อให้เราสามารถกลับเท็จ
>> ตอนนี้เราต้องการทำจริงไบนารี เป็นส่วนหนึ่งของการค้นหาค้นหาแบบไบนารี
ดังนั้นเราจึงต้องการที่จะหาตรงกลาง องค์ประกอบของอาร์เรย์นี้
ที่นี่เราพูดกลางเท่ากับ n แบ่ง 2 เนื่องจากองค์ประกอบตรงกลางเป็น
จะเป็นความยาวของ อาเรย์ของเราหารด้วย 2
ตอนนี้เรากำลังจะตรวจสอบเพื่อดูว่า องค์ประกอบกลางเท่ากับค่าที่เรากำลัง
ค้นหา
ดังนั้นหากค่ากลางเท่ากับค่าเรา สามารถกลับจริงตั้งแต่ที่เราพบ
ค่าในอาเรย์ของเรา
>> แต่ถ้าที่ไม่เป็นความจริงตอนนี้ ที่เราต้องทำซ้ำ
ขั้นตอนของการค้นหาแบบไบนารี
เราจำเป็นต้องค้นหาอย่างใดอย่างหนึ่งที่จะ ด้านซ้ายของแถวหรือ
ตรงกลางของแถว
ดังนั้นที่นี่เราบอกว่าถ้าค่าที่ตรงกลางเป็น น้อยกว่าค่าที่หมายถึงค่าที่
มากกว่าตรงกลาง ของอาร์เรย์
ดังนั้นจะต้องมีค่าทางด้านขวาของ องค์ประกอบที่เราก็มองไปที่
>> ดังนั้นที่นี่เรากำลังจะ ค้นหาซ้ำ
และเราจะดูที่สิ่งที่เรากำลังผ่าน นี้ในครั้งที่สอง
แต่เรากำลังจะค้นหาเพื่อ ที่เหมาะสมขององค์ประกอบกลาง
และในกรณีอื่น ๆ ที่หมายความว่า ค่าน้อยกว่าตรงกลางของ
อาเรย์และอื่น ๆ ที่เรากำลังจะ เพื่อค้นหาทางด้านซ้าย
ตอนนี้ด้านซ้ายเป็นไปได้ บิตง่ายต่อการมองไปที่
ดังนั้นเราเห็นที่นี่ว่าเราซ้ำ ค้นหาเรียกครั้งแรกที่
อาร์กิวเมนต์เป็นอีกครั้งค่า เรากำลังมองหาในช่วง
อาร์กิวเมนต์ที่สองเป็นไปได้ อาร์เรย์ที่เราค้นหาผ่าน
และองค์ประกอบสุดท้ายในขณะนี้คือตรงกลาง
โปรดจำไว้ว่าพารามิเตอร์สุดท้ายคือ int ของเรา n เพื่อให้เป็นความยาวของอาร์เรย์ของเรา
>> ในการเรียกร้องซ้ำในการค้นหาเรา บอกว่าตอนนี้ความยาวของ
แถวกลาง
ดังนั้นถ้าอาร์เรย์ของเราคือขนาด 20 และเรา ค้นหาที่ดัชนี 10 ตั้งแต่กลางเป็น
20 หารด้วย 2 นั่นหมายความว่าเรากำลัง 10 ผ่านใหม่
ความยาวของอาร์เรย์ของเรา
โปรดจำไว้ว่าเมื่อคุณมีอาร์เรย์ ความยาว 10 นั่นหมายความว่าถูกต้อง
องค์ประกอบในดัชนี 0 ถึง 9
ดังนั้นนี่คือสิ่งที่เราต้องการ ระบุอาร์เรย์การปรับปรุงของเรา - ซ้าย
อาร์เรย์จากองค์ประกอบกลาง
>> ดังนั้นมองไปทางขวาเป็น บิตยากขึ้น
ตอนแรกให้พิจารณาระยะเวลา ของอาร์เรย์ที่ด้านขวาของ
องค์ประกอบกลาง
ดังนั้นถ้าอาร์เรย์ของเราคือขนาด n แล้​​ว แถวใหม่จะมีขนาด n ลบ
กลางลบ 1
ดังนั้นขอคิด n ลบกลาง
>> อีกครั้งถ้าอาร์เรย์มีขนาด 20 และ เราหารด้วย 2 จะได้รับตรงกลาง
เพื่อให้ตรงกลางเป็น 10 แล้ว n ลบกลาง เป็นไปเพื่อให้เรามี 10 ดังนั้น 10
องค์ประกอบทางด้านขวาของกลาง
แต่เรายังมีลบนี้ 1 เนื่องจากเราไม่ต้องการที่จะ
รวมถึงตัวเองกลาง
ดังนั้น n ลบลบ 1 ตรงกลางจะช่วยให้เรา จำนวนรวมขององค์ประกอบทางด้านขวา
ของดัชนีกลางในอาร์เรย์
>> ตอนนี้ที่นี่จำไว้ว่ากลาง พารามิเตอร์เป็นอาร์เรย์ค่า
ดังนั้นที่นี่เรากำลังผ่าน การปรับปรุงค่าอาร์เรย์
ค่านี้บวกกลางบวก 1 จริงว่าเรียกซ้ำ
ค้นหาผ่านในอาร์เรย์ใหม่ที่ ที่แถวใหม่จะเริ่มต้นในช่วงกลาง
บวกหนึ่งของอาร์เรย์ค่านิยมของเราที่เป็นต้นฉบับ
>> ไวยากรณ์สำรองสำหรับว่าตอนนี้ที่ คุณได้เริ่มต้นที่จะเห็นตัวชี้เป็น
ค่ากลางเครื่องหมายบวก 1
ดังนั้นคว้าที่อยู่ตรงกลางของ บวกองค์ประกอบหนึ่งของค่า
>> ตอนนี้ถ้าคุณไม่สบาย การปรับเปลี่ยนอาร์เรย์ที่ชอบคุณ
นอกจากนี้ยังอาจมีการดำเนินการโดยใช้ ฟังก์ชั่นช่วยซ้ำที่
ฟังก์ชั่นที่จะช่วย การขัดแย้งมากขึ้น
ดังนั้นแทนการเพียงแค่ค่า อาเรย์และขนาดของอาร์เรย์
ฟังก์ชั่นผู้ช่วยอาจจะใช้เวลามากขึ้น ขัดแย้งรวมทั้งดัชนีที่ต่ำกว่า
ที่คุณจะดูแลเกี่ยวกับในอาร์เรย์ และดัชนีบนที่คุณสนใจ
เกี่ยวกับอาเรย์
>> และเพื่อให้การติดตามของทั้งสองที่ต่ำกว่า ดัชนีและดัชนีบนที่คุณทำไม่ได้
ต้องเคยแก้ไข อาร์เรย์ค่าเดิม
คุณก็สามารถดำเนินการต่อไป ใช้อาร์เรย์ค่า
แต่ที่นี่สังเกตเห็นเราไม่จำเป็นต้องช่วย ทำงานตราบใดที่เรา
ยินดีที่จะปรับเปลี่ยนเดิม อาร์เรย์ค่า
เรายินดีที่จะผ่านใน ค่าปรับปรุง
>> ตอนนี้เราไม่สามารถค้นหา binary กว่า อาเรย์ที่ไม่ได้คัดแยก
ดังนั้นขอได้รับนี้แยกออก
ตอนนี้สังเกตเห็นการจัดเรียงที่ผ่านมาสอง int ค่าพารามิเตอร์ซึ่งเป็น
อาร์เรย์ที่เรากำลังเรียงลำดับและ int n, ซึ่งเป็นความยาวของแถวที่
เรากำลังการเรียงลำดับ
ดังนั้นที่นี่เราต้องการที่จะใช้ ขั้นตอนวิธีการเรียงลำดับ
ที่เป็นของ n o ยกกำลัง
คุณสามารถเลือกเรียงลำดับฟองเลือก เรียงลำดับหรือการจัดเรียงแทรกหรือ
บางประเภทอื่น ๆ ที่เรายังไม่ได้ ที่เห็นในชั้นเรียน
แต่ที่นี่เราจะ การเลือกใช้ประเภท
>> ดังนั้นเรากำลังจะย้ำ ช่วงอาร์เรย์ทั้งหมด
ดีที่นี่เราจะเห็นว่าเรากำลัง iterating จาก 0 ถึง n ลบ 1
ทำไมไม่ไปตลอดทางถึง n?
ดีถ้าเราได้เรียงลำดับแล้วเป็นครั้งแรก n ลบ 1 องค์ประกอบแล้ว
องค์ประกอบสุดท้ายมากแล้วสิ่งที่จะต้อง ในสถานที่ที่ถูกต้องเพื่อให้การเรียงลำดับไป
อาร์เรย์ทั้งหมด
>> ตอนนี้จำได้ว่าการเลือก ผลงานการจัดเรียง
เรากำลังจะไปกว่าอาร์เรย์ทั้งหมด มองหาค่าต่ำสุดใน
อาร์เรย์และติดที่ ในขั้นต้น
จากนั้นเราจะไปกว่าทั้ง อาเรย์อีกครั้งมองหาที่สอง
องค์ประกอบที่เล็กที่สุดและติดที่ อยู่ในตำแหน่งที่สองใน
อาเรย์และอื่น ๆ
ดังนั้นนั่นคือสิ่งที่จะทำนี้
>> ที่นี่เราจะเห็นว่าเรา การตั้งค่าขั้นต่ำในปัจจุบัน
ค่าดัชนีลำดับที่ i
ดังนั้นในการทำซ้ำเป็นครั้งแรกที่เรากำลังจะ ที่จะต้องพิจารณาค่าต่ำสุดจะเป็น
จุดเริ่มต้นของอาเรย์ของเรา
จากนั้นเราจะย้ำกว่า ส่วนที่เหลือของอาร์เรย์, การตรวจสอบเพื่อ
ดูว่ามีองค์ประกอบใด ๆ ที่มีขนาดเล็กกว่า อย่างใดอย่างหนึ่งที่เรากำลัง
พิจารณาขั้นต่ำ
>> ดังนั้นที่นี่ค่าเจบวกหนึ่ง - ที่ น้อยกว่าสิ่งที่เรามีอยู่ในปัจจุบัน
พิจารณาขั้นต่ำ
แล้วเรากำลังจะปรับปรุงสิ่งที่ เราคิดว่าเป็นขั้นต่ำที่
ดัชนีเจบวก 1
ดังนั้นทำอย่างไรที่ทั่วอาร์เรย์ทั้งหมด และหลังจากนี้สำหรับวงต่ำสุด
ควรจะเป็นองค์ประกอบขั้นต่ำจาก ตำแหน่งลำดับที่ i ในอาร์เรย์
>> เมื่อเรามีที่เราสามารถสลับ ค่าต่ำสุดในตำแหน่งลำดับที่ i
ในอาร์เรย์
ดังนั้นนี้เป็นเพียงการแลกเปลี่ยนมาตรฐาน
เราเก็บไว้ในค่าชั่วคราว - ค่าลำดับที่ i ในอาร์เรย์ -
ใส่ลงไปในค่าลำดับที่ i ในอาร์เรย์ ค่าต่ำสุดที่เป็นมี
แล้วเก็บกลับเข้ามาในที่ ค่าต่ำสุดในปัจจุบันที่ใช้จะเป็น
ค่า i th-ในอาร์เรย์ดังนั้น ว่าเราไม่ได้สูญเสียมันไป
>> ดังนั้นที่ยังคงอยู่กับ ซ้ำไป
เราจะเริ่มมองหาที่สอง ค่าต่ำสุดและใส่ที่เป็น
ตำแหน่งที่สอง
ซ้ำสามเราจะมองหา ค่าต่ำสุดที่สามและแทรก
ที่เป็นตำแหน่งที่สามและอื่น จนกระทั่งเรามีอาร์เรย์ที่เรียงลำดับ
ชื่อของฉันคือร็อบและ เป็นประเภทที่เลือก