[เล่นเพลง] 

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