>> [เล่นเพลง]
>> DOUG LLOYD: สิทธิทั้งหมด
ดังนั้นการค้นหาแบบไบนารีเป็น ขั้นตอนวิธีการที่เราสามารถใช้
เพื่อหาองค์ประกอบภายในของอาร์เรย์
ซึ่งแตกต่างจากการค้นหาเชิงเส้นมันต้องมี เงื่อนไขพิเศษได้พบกันก่อน
แต่ก็เพื่อให้มีประสิทธิภาพมากขึ้นถ้า สภาพที่ในความเป็นจริงพบ
>> ดังนั้นสิ่งที่เป็นความคิดที่นี่?
มันแบ่งและพิชิต
เราต้องการที่จะลดขนาดของ พื้นที่ค้นหาโดยครึ่งหนึ่งในแต่ละครั้ง
เพื่อหาจำนวนเป้าหมาย
ซึ่งเป็นที่ที่มีเงื่อนไขว่า มาลงเล่น แต่
เราสามารถใช้ประโยชน์จากพลังของ ขจัดครึ่งหนึ่งขององค์ประกอบ
โดยไม่ได้มองไปที่ พวกเขาหากอาร์เรย์จะถูกจัดเรียง
>> ถ้ามันเป็นส่วนผสมที่สมบูรณ์ขึ้น เราก็ไม่สามารถออกจากมือ
ทิ้งครึ่งหนึ่งขององค์ประกอบเพราะ เราไม่ทราบว่าสิ่งที่เรากำลังทิ้ง
แต่ถ้าอาร์เรย์จะถูกเรียงลำดับ เราสามารถทำเช่นนั้นเพราะเรา
รู้ทุกอย่างไปที่ ด้านซ้ายของที่เรามีอยู่ในปัจจุบัน
จะต้องต่ำกว่า ค่าเราในขณะนี้ที่
และทุกอย่างไป ด้านขวาของที่เรามี
ต้องมากกว่าค่า เรากำลังมองหาที่
>> ดังนั้นสิ่งที่ pseudocode ขั้นตอนในการค้นหาแบบไบนารี?
เราทำซ้ำขั้นตอนนี้จนกว่าจะมีการ อาร์เรย์หรือในขณะที่เราดำเนินการผ่าน
อาร์เรย์ย่อยของชิ้นเล็ก ๆ อาร์เรย์เดิมมีขนาด 0
คำนวณจุดกึ่งกลาง ของกระแสอาร์เรย์ย่อย
>> ถ้าค่าที่คุณกำลังมองหาคือ ในองค์ประกอบของอาร์เรย์ที่หยุด
คุณพบว่า.
นั่นวิเศษมาก
มิฉะนั้นถ้าเป้าหมายคือ น้อยกว่าสิ่งที่อยู่ที่ตรงกลาง
ดังนั้นหากค่าที่เรากำลังมองหา สำหรับเป็นต่ำกว่าสิ่งที่เราเห็น
ทำซ้ำขั้นตอนนี้อีกครั้ง แต่ เปลี่ยนจุดสิ้นสุดแทน
ของการเป็นต้นฉบับ อาร์เรย์เสร็จสมบูรณ์เต็มรูปแบบ
จะเป็นเพียงไปทางซ้าย ของที่เราเพียงแค่มอง
>> เรารู้ว่าตรงกลางอยู่ในระดับสูงเกินไป หรือเป้าหมายน้อยกว่าตรงกลาง
และดังนั้นจึงต้องมีอยู่ถ้ามัน อยู่ที่ทุกคนในอาร์เรย์
ที่ไหนสักแห่งทางด้านซ้ายของจุดกึ่งกลางที่
และเพื่อให้เราจะตั้งแถว สถานที่ตั้งเพียงไปทางซ้าย
จุดกึ่งกลางของเป็นจุดสิ้นสุดใหม่
ตรงกันข้ามถ้าเป้าหมายคือ มากกว่าสิ่งที่อยู่ที่ตรงกลาง
เราทำเดียวกันแน่นอน กระบวนการ แต่แทนที่จะเรา
เปลี่ยนจุดเริ่มต้นที่จะเป็น เพียงแค่ไปทางขวาของจุดกึ่งกลางที่
เราคำนวณเพียง
และจากนั้นเราจะเริ่มกระบวนการใหม่อีกครั้ง
>> ลองเห็นภาพนี้ OK?
เพื่อให้มีจำนวนมากที่ไปและที่นี่ แต่นี่เป็นอาร์เรย์ของ 15 องค์ประกอบ
และเรากำลังจะได้รับการติดตาม จำนวนมากของสิ่งอื่น ๆ อีกเวลานี้
ดังนั้นในการค้นหาเชิงเส้นเรา เพียงดูแลเกี่ยวกับเป้าหมาย
แต่เวลานี้เราต้องการที่จะ ดูแลเกี่ยวกับการที่เราจะอยู่ที่ไหน
เริ่มที่จะมองที่ เราหยุดมอง
และสิ่งที่จุดกึ่งกลาง ของอาร์เรย์ปัจจุบัน
ดังนั้นที่นี่เราไปกับการค้นหาแบบไบนารี
เราสวยมากดีที่จะไปใช่ไหม?
ฉันแค่ไปที่จะวางลง ด้านล่างนี่ชุดของดัชนี
นี้เป็นเพียงสิ่งที่องค์ประกอบ ของอาร์เรย์เรากำลังพูดถึง
กับการค้นหาเชิงเส้นเรา ดูแลดังนั้นเรา
จำเป็นต้องทราบจำนวน องค์ประกอบที่เรากำลังทำซ้ำไป
แต่เราไม่สนใจสิ่งที่จริง องค์ประกอบที่เรากำลังมองหาที่
ในการค้นหาไบนารีที่เราทำ
และเพื่อให้ผู้ที่มีเพียง มีเป็นคู่มือเล็ก ๆ น้อย ๆ
>> ดังนั้นเราจึงสามารถเริ่มต้นใช่มั้ย?
ก็ไม่มาก
โปรดจำไว้ว่าสิ่งที่ผมพูด เกี่ยวกับการค้นหาแบบไบนารี?
เราไม่สามารถทำมันได้ใน อาเรย์ไม่ได้เรียงลำดับหรืออื่น
เราไม่ได้รับประกันว่า องค์ประกอบบางอย่างหรือค่าไม่ได้
เป็นบังเอิญ ทิ้งเมื่อเราเพียง
ตัดสินใจที่จะไม่สนใจครึ่งหนึ่งของอาร์เรย์
>> ดังนั้นขั้นตอนหนึ่งที่มีการค้นหาแบบไบนารี คือคุณต้องมีอาร์เรย์เรียง
และคุณสามารถใช้ใด ๆ ของการเรียงลำดับ ขั้นตอนวิธีการที่เราได้พูดคุยเกี่ยวกับ
จะได้รับคุณไปยังตำแหน่งที่
ดังนั้นตอนนี้เราอยู่ในตำแหน่งที่ เราสามารถดำเนินการค้นหาแบบทวิภาค
>> ดังนั้นขอให้ทำซ้ำขั้นตอน ทีละขั้นตอนและให้
การติดตามของสิ่งที่เกิดขึ้นในขณะที่เราไป
ดังนั้นแรกที่เราต้องทำคือการคำนวณ จุดกึ่งกลางของแถวปัจจุบัน
ดีเราจะพูดว่าเราเป็นครั้งแรกของ ทั้งหมดที่กำลังมองหา 19 ค่า
เราพยายามที่จะหาจำนวน 19
องค์ประกอบแรกนี้ อาเรย์ตั้งอยู่ที่ดัชนีศูนย์
และองค์ประกอบสุดท้ายนี้ ตั้งอยู่อาร์เรย์ที่ 14 ดัชนี
และเพื่อให้เราจะเรียกผู้ที่เริ่มต้นและสิ้นสุด
>> ดังนั้นเราจะคำนวณจากจุดกึ่งกลาง เพิ่ม 0 บวก 14 หารด้วย 2;
จุดกึ่งกลางตรงไปตรงสวย
และเราสามารถพูดได้ว่า จุดกึ่งกลางคือตอนที่ 7
ดังนั้นคือ 15 สิ่งที่เรากำลังมองหา?
ไม่มันไม่ใช่.
เรากำลังมองหา 19
แต่เรารู้ว่า 19 จะสูงกว่า กว่าสิ่งที่เราพบได้ที่ตรงกลาง
>> ดังนั้นสิ่งที่เราสามารถทำได้คือ เปลี่ยนจุดเริ่มต้น
จะเป็นเพียงไปทางขวาของ จุดกึ่งกลางและทำซ้ำขั้นตอนอีกครั้ง
และเมื่อเราทำอย่างนั้นตอนนี้เราพูด จุดเริ่มต้นใหม่เป็นที่ตั้งอาร์เรย์ 8
สิ่งที่เราได้ทำอย่างมีประสิทธิภาพคือ ละเว้นทุกอย่างทางด้านซ้ายของ 15
เราได้ตัดออกครึ่งหนึ่ง ของปัญหาและตอนนี้
แทนที่จะต้องค้นหา กว่า 15 องค์ประกอบในอาร์เรย์ของเรา
เราจะต้องค้นหากว่า 7
ดังนั้น 8 เป็นจุดเริ่มต้นใหม่
14 ยังคงเป็นจุดสิ้นสุด
>> และตอนนี้เราไปมากกว่านี้อีกครั้ง
เราคำนวณจุดกึ่งกลางใหม่
บวก 8 14 22 หารด้วย 2 11
นี้คือสิ่งที่เรากำลังมองหา?
ไม่มันไม่ใช่.
เรากำลังมองหาค่าที่เป็น น้อยกว่าสิ่งที่เราพบเพียง
ดังนั้นเรากำลังจะทำซ้ำ กระบวนการใหม่อีกครั้ง
เรากำลังจะเปลี่ยนจุดสิ้นสุดในการ เป็นเพียงทางด้านซ้ายของจุดกึ่งกลางที่
ดังนั้นจุดสิ้นสุดใหม่จะกลายเป็น 10
และตอนนี้ว่าเป็นเพียงส่วนหนึ่งของ อาร์เรย์ที่เรามีการจัดเรียงผ่าน
ดังนั้นเราจึงได้ตัดออกในขณะนี้ 12 จาก 15 องค์ประกอบ
เรารู้ว่าถ้า 19 ที่มีอยู่ในอาร์เรย์มัน
จะต้องมีอยู่ที่ไหนสักแห่งระหว่างองค์ประกอบ หมายเลข 8 และองค์ประกอบจำนวน 10
>> ดังนั้นเราจึงคำนวณจุดกึ่งกลางใหม่อีกครั้ง
8 บวก 10 คือ 18 หารด้วย 2 คือ 9
และในกรณีนี้ให้ดูที่ เป้าหมายอยู่ที่ตรงกลาง
เราพบว่าสิ่งที่เรากำลังมองหา
เราสามารถหยุด
เราประสบความสำเร็จ การค้นหาแบบไบนารี
ทั้งหมดขวา
ดังนั้นเราจึงรู้ขั้นตอนวิธีนี้ ทำงานถ้าเป้าหมายคือ
ที่ไหนสักแห่งภายในของอาร์เรย์
ขั้นตอนวิธีการทำงานว่านี้ เป้าหมายไม่ได้อยู่ในแถว?
ดีขอเริ่มต้น อีกครั้งและเวลานี้
ให้ดูสำหรับองค์ประกอบ 16 ซึ่งสายตาเราสามารถมองเห็น
ไม่มีที่ใดก็ได้ในอาร์เรย์
>> จุดเริ่มต้นเป็นอีกครั้งที่ 0
จุดสิ้นสุดเป็นอีกครั้งที่ 14
ผู้ที่มีดัชนีในครั้งแรกและ องค์ประกอบสุดท้ายของอาร์เรย์สมบูรณ์
และเราจะไปผ่านกระบวนการที่เราเพียง ผ่านไปอีกครั้งพยายามที่จะหา 16
แม้ว่าสายตาที่เราสามารถทำได้อยู่แล้ว บอกว่ามันไม่ได้ไปอยู่ที่นั่น
เราเพียงแค่ต้องการให้แน่ใจว่าขั้นตอนวิธีนี้ จะในความเป็นจริงยังคงทำงานในทางใดทางหนึ่ง
และไม่เพียง แต่ปล่อยให้เรา ติดอยู่ในวง จำกัด
>> ดังนั้นสิ่งที่เป็นขั้นตอนแรก?
คำนวณจุดกึ่งกลาง ของอาร์เรย์ปัจจุบัน
อะไรจุดกึ่งกลาง ของอาร์เรย์ปัจจุบันหรือไม่?
ดีก็ 7 ใช่มั้ย?
บวก 14 หารด้วย 0 2 7
15 สิ่งที่เรากำลังมองหา?
เลขที่
มันใกล้สวย แต่เรากำลังมองหา สำหรับค่าใหญ่กว่าเล็กน้อยว่า
>> ดังนั้นเรารู้ว่ามันเป็นไปได้ จะไม่มีที่ไหนเลยที่ด้านซ้ายของ 15
เป้าหมายมากกว่า สิ่งที่อยู่ในจุดกึ่งกลาง
และเพื่อให้เรากำหนดจุดเริ่มต้นใหม่ที่จะ เป็นเพียงแค่ไปทางขวาของกลาง
จุดกึ่งกลางในปัจจุบันคือ 7 ดังนั้น สมมติว่าจุดเริ่มต้นใหม่คือ 8
และสิ่งที่เราได้อย่างมีประสิทธิภาพ ทำอีกครั้งจะถูกละเว้น
ครึ่งซ้ายทั้งหมดของอาร์เรย์
>> ตอนนี้เราทำซ้ำ ดำเนินการอย่างใดอย่างหนึ่งเวลามากขึ้น
คำนวณจุดกึ่งกลางใหม่
บวก 8 14 22 หารด้วย 2 11
23 สิ่งที่เรากำลังมองหา?
แต่น่าเสียดายที่ไม่มี
เรากำลังมองหาค่า ที่น้อยกว่า 23
และดังนั้นในกรณีนี้เราจะ ที่จะเปลี่ยนจุดสิ้นสุดจะเป็นเพียง
ที่ด้านซ้ายของจุดกึ่งกลางในปัจจุบัน
จุดกึ่งกลางในปัจจุบันคือ 11 และ ดังนั้นเราจะตั้งจุดสิ้นสุดใหม่
สำหรับครั้งต่อไปที่เราจะไป ผ่านขั้นตอนนี้ถึง 10
>> อีกครั้งที่เราจะไปผ่านกระบวนการอีกครั้ง
คำนวณจุดกึ่งกลาง
8 บวก 10 หารด้วย 2 คือ 9
19 สิ่งที่เรากำลังมองหา?
แต่น่าเสียดายที่ไม่มี
เรายังคงมองหา จำนวนน้อยกว่า
ดังนั้นเราจะเปลี่ยนจุดสิ้นสุดเวลานี้ จะเป็นเพียงทางด้านซ้ายของจุดกึ่งกลางที่
จุดกึ่งกลางในขณะนี้ 9 ดังนั้นจุดสิ้นสุดจะ 8
และตอนนี้เรากำลังเพียงแค่มอง ที่อาร์เรย์องค์ประกอบหนึ่ง
>> อะไรจุดกึ่งกลางของอาร์เรย์นี้หรือไม่?
ดีก็เริ่มต้นที่ 8 มัน สิ้นสุดที่ 8 จุดกึ่งกลางคือ 8
นั่นคือสิ่งที่เรากำลังมองหา?
เรากำลังมองหา 17
ไม่มีเรากำลังมองหา 16
ดังนั้นถ้ามันมีอยู่ในอาร์เรย์ มันต้องมีอยู่ที่ไหนสักแห่ง
ด้านซ้ายของที่เรามีอยู่ในปัจจุบัน
ดังนั้นสิ่งที่เราจะทำอย่างไร
ดีที่เราจะตั้งจุดสิ้นสุดจะเป็นเพียง ที่ด้านซ้ายของจุดกึ่งกลางในปัจจุบัน
ดังนั้นเราจะเปลี่ยนจุดสิ้นสุด 7
คุณเห็นสิ่งที่เพิ่ง เกิดขึ้นที่นี่ แต่?
เงยหน้าขึ้นมองที่นี่ตอนนี้
>> เริ่มต้นอยู่ในขณะนี้สูงกว่าปลาย
ได้อย่างมีประสิทธิภาพปลายทั้งสองข้าง ของอาร์เรย์ของเราได้ข้าม
และเป็นจุดเริ่มต้นคือ ขณะนี้หลังจากจุดสิ้นสุด
ดีที่ไม่ได้ ทำให้รู้สึกใด ๆ ใช่มั้ย?
ดังนั้นตอนนี้สิ่งที่เราสามารถพูดได้ก็คือเรา มีอาร์เรย์ย่อยขนาด 0
และเมื่อเรากำลังอากาศ จุดนี้ที่เราสามารถทำได้ในขณะนี้
รับประกันองค์ประกอบที่ 16 ไม่อยู่ในอาร์เรย์
เพราะจุดเริ่มต้น และจุดสิ้นสุดได้ข้าม
และดังนั้นจึงไม่ได้มี
ตอนนี้สังเกตเห็นว่านี้เป็นเพียงเล็กน้อย แตกต่างจากจุดเริ่มต้นและสิ้นสุด
ชี้เป็นเหมือนกัน
ถ้าเราได้รับการมอง 17 ก็จะมี
รับในอาร์เรย์และเป็นจุดเริ่มต้น และจุดสิ้นสุดของการทำซ้ำที่ผ่านมา
ก่อนที่จะจุดเหล่านั้นข้าม เราจะได้พบมี 17
ก็ต่อเมื่อพวกเขาข้ามที่เราสามารถทำได้ รับประกันได้ว่าองค์ประกอบไม่ได้
อยู่ในอาร์เรย์
>> ดังนั้นขอให้ใช้เวลามากน้อย ขั้นตอนกว่าการค้นหาเชิงเส้น
ในสถานการณ์ที่เลวร้ายที่สุดกรณีที่เรามี การแยกรายชื่อขององค์ประกอบ n
ซ้ำแล้วซ้ำอีกในช่วงครึ่งปีที่จะหาเป้าหมาย เพราะองค์ประกอบเป้าหมาย
จะเป็นหนึ่งในที่ผ่านมา หารหรือมันไม่ได้อยู่ที่ทุกคน
ดังนั้นในกรณีที่เลวร้ายที่สุดที่เราต้อง แยก array-- ที่คุณรู้หรือไม่?
เข้าสู่ระบบครั้ง n; เรา ต้องตัดปัญหา
ในช่วงครึ่งปีจำนวนหนึ่งครั้ง
จำนวนครั้งนั่นคือ n ล็อก
>> สถานการณ์กรณีที่ดีที่สุดคืออะไร?
ดีครั้งแรกที่เรา คำนวณจุดกึ่งกลาง,
เราพบว่าสิ่งที่เรากำลังมองหา
ในทุกที่แล้ว ตัวอย่างในการค้นหาแบบไบนารี
เราได้ไปเพียงกว่าถ้าเรามี รับการมองหาองค์ประกอบที่ 15
เราจะพบว่าการได้ทันที
นั่นคือที่จุดเริ่มต้น
นั่นคือจุดกึ่งกลางของ ความพยายามครั้งแรกที่แยก
ส่วนในการค้นหาไบนารี
>> และในที่เลวร้ายที่สุด กรณีการค้นหาแบบไบนารีทำงาน
n ในการเข้าสู่ระบบที่ดีขึ้นเป็นอย่างมาก กว่าการค้นหาเชิงเส้นในกรณีที่เลวร้ายที่สุด
ในกรณีที่ดีที่สุดไบนารี ค้นหาทำงานในโอเมก้า 1
ดังนั้นการค้นหาแบบไบนารีเป็นจำนวนมาก ดีกว่าการค้นหาเชิงเส้น
แต่คุณต้องจัดการกับกระบวนการของ การเรียงลำดับอาร์เรย์ของคุณก่อนที่คุณสามารถ
ใช้ประโยชน์จากพลังของการค้นหาไบนารี
>> ฉันลอยด์ดั๊ก
นี่คือซี 50