1
00:00:00,000 --> 00:00:03,346
>> [เล่นเพลง]

2
00:00:03,346 --> 00:00:05,258

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: สิทธิทั้งหมด

4
00:00:06,220 --> 00:00:08,140
ดังนั้นการค้นหาแบบไบนารีเป็น
ขั้นตอนวิธีการที่เราสามารถใช้

5
00:00:08,140 --> 00:00:10,530
เพื่อหาองค์ประกอบภายในของอาร์เรย์

6
00:00:10,530 --> 00:00:14,710
ซึ่งแตกต่างจากการค้นหาเชิงเส้นมันต้องมี
เงื่อนไขพิเศษได้พบกันก่อน

7
00:00:14,710 --> 00:00:19,020
แต่ก็เพื่อให้มีประสิทธิภาพมากขึ้นถ้า
สภาพที่ในความเป็นจริงพบ

8
00:00:19,020 --> 00:00:20,470
>> ดังนั้นสิ่งที่เป็นความคิดที่นี่?

9
00:00:20,470 --> 00:00:21,780
มันแบ่งและพิชิต

10
00:00:21,780 --> 00:00:25,100
เราต้องการที่จะลดขนาดของ
พื้นที่ค้นหาโดยครึ่งหนึ่งในแต่ละครั้ง

11
00:00:25,100 --> 00:00:27,240
เพื่อหาจำนวนเป้าหมาย

12
00:00:27,240 --> 00:00:29,520
ซึ่งเป็นที่ที่มีเงื่อนไขว่า
มาลงเล่น แต่

13
00:00:29,520 --> 00:00:32,740
เราสามารถใช้ประโยชน์จากพลังของ
ขจัดครึ่งหนึ่งขององค์ประกอบ

14
00:00:32,740 --> 00:00:36,070
โดยไม่ได้มองไปที่
พวกเขาหากอาร์เรย์จะถูกจัดเรียง

15
00:00:36,070 --> 00:00:39,200
>> ถ้ามันเป็นส่วนผสมที่สมบูรณ์ขึ้น
เราก็ไม่สามารถออกจากมือ

16
00:00:39,200 --> 00:00:42,870
ทิ้งครึ่งหนึ่งขององค์ประกอบเพราะ
เราไม่ทราบว่าสิ่งที่เรากำลังทิ้ง

17
00:00:42,870 --> 00:00:45,624
แต่ถ้าอาร์เรย์จะถูกเรียงลำดับ
เราสามารถทำเช่นนั้นเพราะเรา

18
00:00:45,624 --> 00:00:48,040
รู้ทุกอย่างไปที่
ด้านซ้ายของที่เรามีอยู่ในปัจจุบัน

19
00:00:48,040 --> 00:00:50,500
จะต้องต่ำกว่า
ค่าเราในขณะนี้ที่

20
00:00:50,500 --> 00:00:52,300
และทุกอย่างไป
ด้านขวาของที่เรามี

21
00:00:52,300 --> 00:00:55,040
ต้องมากกว่าค่า
เรากำลังมองหาที่

22
00:00:55,040 --> 00:00:58,710
>> ดังนั้นสิ่งที่ pseudocode
ขั้นตอนในการค้นหาแบบไบนารี?

23
00:00:58,710 --> 00:01:02,310
เราทำซ้ำขั้นตอนนี้จนกว่าจะมีการ
อาร์เรย์หรือในขณะที่เราดำเนินการผ่าน

24
00:01:02,310 --> 00:01:07,740
อาร์เรย์ย่อยของชิ้นเล็ก ๆ
อาร์เรย์เดิมมีขนาด 0

25
00:01:07,740 --> 00:01:10,960
คำนวณจุดกึ่งกลาง
ของกระแสอาร์เรย์ย่อย

26
00:01:10,960 --> 00:01:14,460
>> ถ้าค่าที่คุณกำลังมองหาคือ
ในองค์ประกอบของอาร์เรย์ที่หยุด

27
00:01:14,460 --> 00:01:15,030
คุณพบว่า.

28
00:01:15,030 --> 00:01:16,550
นั่นวิเศษมาก

29
00:01:16,550 --> 00:01:19,610
มิฉะนั้นถ้าเป้าหมายคือ
น้อยกว่าสิ่งที่อยู่ที่ตรงกลาง

30
00:01:19,610 --> 00:01:23,430
ดังนั้นหากค่าที่เรากำลังมองหา
สำหรับเป็นต่ำกว่าสิ่งที่เราเห็น

31
00:01:23,430 --> 00:01:26,780
ทำซ้ำขั้นตอนนี้อีกครั้ง แต่
เปลี่ยนจุดสิ้นสุดแทน

32
00:01:26,780 --> 00:01:29,300
ของการเป็นต้นฉบับ
อาร์เรย์เสร็จสมบูรณ์เต็มรูปแบบ

33
00:01:29,300 --> 00:01:34,110
จะเป็นเพียงไปทางซ้าย
ของที่เราเพียงแค่มอง

34
00:01:34,110 --> 00:01:38,940
>> เรารู้ว่าตรงกลางอยู่ในระดับสูงเกินไป
หรือเป้าหมายน้อยกว่าตรงกลาง

35
00:01:38,940 --> 00:01:42,210
และดังนั้นจึงต้องมีอยู่ถ้ามัน
อยู่ที่ทุกคนในอาร์เรย์

36
00:01:42,210 --> 00:01:44,660
ที่ไหนสักแห่งทางด้านซ้ายของจุดกึ่งกลางที่

37
00:01:44,660 --> 00:01:48,120
และเพื่อให้เราจะตั้งแถว
สถานที่ตั้งเพียงไปทางซ้าย

38
00:01:48,120 --> 00:01:51,145
จุดกึ่งกลางของเป็นจุดสิ้นสุดใหม่

39
00:01:51,145 --> 00:01:53,770
ตรงกันข้ามถ้าเป้าหมายคือ
มากกว่าสิ่งที่อยู่ที่ตรงกลาง

40
00:01:53,770 --> 00:01:55,750
เราทำเดียวกันแน่นอน
กระบวนการ แต่แทนที่จะเรา

41
00:01:55,750 --> 00:01:59,520
เปลี่ยนจุดเริ่มต้นที่จะเป็น
เพียงแค่ไปทางขวาของจุดกึ่งกลางที่

42
00:01:59,520 --> 00:02:00,680
เราคำนวณเพียง

43
00:02:00,680 --> 00:02:03,220
และจากนั้นเราจะเริ่มกระบวนการใหม่อีกครั้ง

44
00:02:03,220 --> 00:02:05,220
>> ลองเห็นภาพนี้ OK?

45
00:02:05,220 --> 00:02:08,620
เพื่อให้มีจำนวนมากที่ไปและที่นี่
แต่นี่เป็นอาร์เรย์ของ 15 องค์ประกอบ

46
00:02:08,620 --> 00:02:11,400
และเรากำลังจะได้รับการติดตาม
จำนวนมากของสิ่งอื่น ๆ อีกเวลานี้

47
00:02:11,400 --> 00:02:13,870
ดังนั้นในการค้นหาเชิงเส้นเรา
เพียงดูแลเกี่ยวกับเป้าหมาย

48
00:02:13,870 --> 00:02:15,869
แต่เวลานี้เราต้องการที่จะ
ดูแลเกี่ยวกับการที่เราจะอยู่ที่ไหน

49
00:02:15,869 --> 00:02:18,480
เริ่มที่จะมองที่
เราหยุดมอง

50
00:02:18,480 --> 00:02:21,876
และสิ่งที่จุดกึ่งกลาง
ของอาร์เรย์ปัจจุบัน

51
00:02:21,876 --> 00:02:23,250
ดังนั้นที่นี่เราไปกับการค้นหาแบบไบนารี

52
00:02:23,250 --> 00:02:25,290
เราสวยมากดีที่จะไปใช่ไหม?

53
00:02:25,290 --> 00:02:28,650
ฉันแค่ไปที่จะวางลง
ด้านล่างนี่ชุดของดัชนี

54
00:02:28,650 --> 00:02:32,430
นี้เป็นเพียงสิ่งที่องค์ประกอบ
ของอาร์เรย์เรากำลังพูดถึง

55
00:02:32,430 --> 00:02:34,500
กับการค้นหาเชิงเส้นเรา
ดูแลดังนั้นเรา

56
00:02:34,500 --> 00:02:36,800
จำเป็นต้องทราบจำนวน
องค์ประกอบที่เรากำลังทำซ้ำไป

57
00:02:36,800 --> 00:02:40,010
แต่เราไม่สนใจสิ่งที่จริง
องค์ประกอบที่เรากำลังมองหาที่

58
00:02:40,010 --> 00:02:41,014
ในการค้นหาไบนารีที่เราทำ

59
00:02:41,014 --> 00:02:42,930
และเพื่อให้ผู้ที่มีเพียง
มีเป็นคู่มือเล็ก ๆ น้อย ๆ

60
00:02:42,930 --> 00:02:44,910
>> ดังนั้นเราจึงสามารถเริ่มต้นใช่มั้ย?

61
00:02:44,910 --> 00:02:46,240
ก็ไม่มาก

62
00:02:46,240 --> 00:02:48,160
โปรดจำไว้ว่าสิ่งที่ผมพูด
เกี่ยวกับการค้นหาแบบไบนารี?

63
00:02:48,160 --> 00:02:50,955
เราไม่สามารถทำมันได้ใน
อาเรย์ไม่ได้เรียงลำดับหรืออื่น

64
00:02:50,955 --> 00:02:55,820
เราไม่ได้รับประกันว่า
องค์ประกอบบางอย่างหรือค่าไม่ได้

65
00:02:55,820 --> 00:02:57,650
เป็นบังเอิญ
ทิ้งเมื่อเราเพียง

66
00:02:57,650 --> 00:02:59,920
ตัดสินใจที่จะไม่สนใจครึ่งหนึ่งของอาร์เรย์

67
00:02:59,920 --> 00:03:02,574
>> ดังนั้นขั้นตอนหนึ่งที่มีการค้นหาแบบไบนารี
คือคุณต้องมีอาร์เรย์เรียง

68
00:03:02,574 --> 00:03:05,240
และคุณสามารถใช้ใด ๆ ของการเรียงลำดับ
ขั้นตอนวิธีการที่เราได้พูดคุยเกี่ยวกับ

69
00:03:05,240 --> 00:03:06,700
จะได้รับคุณไปยังตำแหน่งที่

70
00:03:06,700 --> 00:03:10,370
ดังนั้นตอนนี้เราอยู่ในตำแหน่งที่
เราสามารถดำเนินการค้นหาแบบทวิภาค

71
00:03:10,370 --> 00:03:12,560
>> ดังนั้นขอให้ทำซ้ำขั้นตอน
ทีละขั้นตอนและให้

72
00:03:12,560 --> 00:03:14,830
การติดตามของสิ่งที่เกิดขึ้นในขณะที่เราไป

73
00:03:14,830 --> 00:03:17,980
ดังนั้นแรกที่เราต้องทำคือการคำนวณ
จุดกึ่งกลางของแถวปัจจุบัน

74
00:03:17,980 --> 00:03:20,620
ดีเราจะพูดว่าเราเป็นครั้งแรกของ
ทั้งหมดที่กำลังมองหา 19 ค่า

75
00:03:20,620 --> 00:03:22,290
เราพยายามที่จะหาจำนวน 19

76
00:03:22,290 --> 00:03:25,380
องค์ประกอบแรกนี้
อาเรย์ตั้งอยู่ที่ดัชนีศูนย์

77
00:03:25,380 --> 00:03:28,880
และองค์ประกอบสุดท้ายนี้
ตั้งอยู่อาร์เรย์ที่ 14 ดัชนี

78
00:03:28,880 --> 00:03:31,430
และเพื่อให้เราจะเรียกผู้ที่เริ่มต้นและสิ้นสุด

79
00:03:31,430 --> 00:03:35,387
>> ดังนั้นเราจะคำนวณจากจุดกึ่งกลาง
เพิ่ม 0 บวก 14 หารด้วย 2;

80
00:03:35,387 --> 00:03:36,720
จุดกึ่งกลางตรงไปตรงสวย

81
00:03:36,720 --> 00:03:40,190
และเราสามารถพูดได้ว่า
จุดกึ่งกลางคือตอนที่ 7

82
00:03:40,190 --> 00:03:43,370
ดังนั้นคือ 15 สิ่งที่เรากำลังมองหา?

83
00:03:43,370 --> 00:03:43,940
ไม่มันไม่ใช่.

84
00:03:43,940 --> 00:03:45,270
เรากำลังมองหา 19

85
00:03:45,270 --> 00:03:49,400
แต่เรารู้ว่า 19 จะสูงกว่า
กว่าสิ่งที่เราพบได้ที่ตรงกลาง

86
00:03:49,400 --> 00:03:52,470
>> ดังนั้นสิ่งที่เราสามารถทำได้คือ
เปลี่ยนจุดเริ่มต้น

87
00:03:52,470 --> 00:03:57,280
จะเป็นเพียงไปทางขวาของ
จุดกึ่งกลางและทำซ้ำขั้นตอนอีกครั้ง

88
00:03:57,280 --> 00:04:01,690
และเมื่อเราทำอย่างนั้นตอนนี้เราพูด
จุดเริ่มต้นใหม่เป็นที่ตั้งอาร์เรย์ 8

89
00:04:01,690 --> 00:04:07,220
สิ่งที่เราได้ทำอย่างมีประสิทธิภาพคือ
ละเว้นทุกอย่างทางด้านซ้ายของ 15

90
00:04:07,220 --> 00:04:09,570
เราได้ตัดออกครึ่งหนึ่ง
ของปัญหาและตอนนี้

91
00:04:09,570 --> 00:04:13,510
แทนที่จะต้องค้นหา
กว่า 15 องค์ประกอบในอาร์เรย์ของเรา

92
00:04:13,510 --> 00:04:15,610
เราจะต้องค้นหากว่า 7

93
00:04:15,610 --> 00:04:17,706
ดังนั้น 8 เป็นจุดเริ่มต้นใหม่

94
00:04:17,706 --> 00:04:19,600
14 ยังคงเป็นจุดสิ้นสุด

95
00:04:19,600 --> 00:04:21,430
>> และตอนนี้เราไปมากกว่านี้อีกครั้ง

96
00:04:21,430 --> 00:04:22,810
เราคำนวณจุดกึ่งกลางใหม่

97
00:04:22,810 --> 00:04:27,130
บวก 8 14 22 หารด้วย 2 11

98
00:04:27,130 --> 00:04:28,660
นี้คือสิ่งที่เรากำลังมองหา?

99
00:04:28,660 --> 00:04:30,110
ไม่มันไม่ใช่.

100
00:04:30,110 --> 00:04:32,930
เรากำลังมองหาค่าที่เป็น
น้อยกว่าสิ่งที่เราพบเพียง

101
00:04:32,930 --> 00:04:34,721
ดังนั้นเรากำลังจะทำซ้ำ
กระบวนการใหม่อีกครั้ง

102
00:04:34,721 --> 00:04:38,280
เรากำลังจะเปลี่ยนจุดสิ้นสุดในการ
เป็นเพียงทางด้านซ้ายของจุดกึ่งกลางที่

103
00:04:38,280 --> 00:04:41,800
ดังนั้นจุดสิ้นสุดใหม่จะกลายเป็น 10

104
00:04:41,800 --> 00:04:44,780
และตอนนี้ว่าเป็นเพียงส่วนหนึ่งของ
อาร์เรย์ที่เรามีการจัดเรียงผ่าน

105
00:04:44,780 --> 00:04:48,460
ดังนั้นเราจึงได้ตัดออกในขณะนี้
12 จาก 15 องค์ประกอบ

106
00:04:48,460 --> 00:04:51,550
เรารู้ว่าถ้า 19
ที่มีอยู่ในอาร์เรย์มัน

107
00:04:51,550 --> 00:04:57,210
จะต้องมีอยู่ที่ไหนสักแห่งระหว่างองค์ประกอบ
หมายเลข 8 และองค์ประกอบจำนวน 10

108
00:04:57,210 --> 00:04:59,400
>> ดังนั้นเราจึงคำนวณจุดกึ่งกลางใหม่อีกครั้ง

109
00:04:59,400 --> 00:05:02,900
8 บวก 10 คือ 18 หารด้วย 2 คือ 9

110
00:05:02,900 --> 00:05:05,074
และในกรณีนี้ให้ดูที่
เป้าหมายอยู่ที่ตรงกลาง

111
00:05:05,074 --> 00:05:06,740
เราพบว่าสิ่งที่เรากำลังมองหา

112
00:05:06,740 --> 00:05:07,780
เราสามารถหยุด

113
00:05:07,780 --> 00:05:10,561
เราประสบความสำเร็จ
การค้นหาแบบไบนารี

114
00:05:10,561 --> 00:05:11,060
ทั้งหมดขวา

115
00:05:11,060 --> 00:05:13,930
ดังนั้นเราจึงรู้ขั้นตอนวิธีนี้
ทำงานถ้าเป้าหมายคือ

116
00:05:13,930 --> 00:05:16,070
ที่ไหนสักแห่งภายในของอาร์เรย์

117
00:05:16,070 --> 00:05:19,060
ขั้นตอนวิธีการทำงานว่านี้
เป้าหมายไม่ได้อยู่ในแถว?

118
00:05:19,060 --> 00:05:20,810
ดีขอเริ่มต้น
อีกครั้งและเวลานี้

119
00:05:20,810 --> 00:05:23,380
ให้ดูสำหรับองค์ประกอบ
16 ซึ่งสายตาเราสามารถมองเห็น

120
00:05:23,380 --> 00:05:25,620
ไม่มีที่ใดก็ได้ในอาร์เรย์

121
00:05:25,620 --> 00:05:27,110
>> จุดเริ่มต้นเป็นอีกครั้งที่ 0

122
00:05:27,110 --> 00:05:28,590
จุดสิ้นสุดเป็นอีกครั้งที่ 14

123
00:05:28,590 --> 00:05:32,490
ผู้ที่มีดัชนีในครั้งแรกและ
องค์ประกอบสุดท้ายของอาร์เรย์สมบูรณ์

124
00:05:32,490 --> 00:05:36,057
และเราจะไปผ่านกระบวนการที่เราเพียง
ผ่านไปอีกครั้งพยายามที่จะหา 16

125
00:05:36,057 --> 00:05:39,140
แม้ว่าสายตาที่เราสามารถทำได้อยู่แล้ว
บอกว่ามันไม่ได้ไปอยู่ที่นั่น

126
00:05:39,140 --> 00:05:43,450
เราเพียงแค่ต้องการให้แน่ใจว่าขั้นตอนวิธีนี้
จะในความเป็นจริงยังคงทำงานในทางใดทางหนึ่ง

127
00:05:43,450 --> 00:05:46,310
และไม่เพียง แต่ปล่อยให้เรา
ติดอยู่ในวง จำกัด

128
00:05:46,310 --> 00:05:48,190
>> ดังนั้นสิ่งที่เป็นขั้นตอนแรก?

129
00:05:48,190 --> 00:05:50,230
คำนวณจุดกึ่งกลาง
ของอาร์เรย์ปัจจุบัน

130
00:05:50,230 --> 00:05:52,790
อะไรจุดกึ่งกลาง
ของอาร์เรย์ปัจจุบันหรือไม่?

131
00:05:52,790 --> 00:05:54,410
ดีก็ 7 ใช่มั้ย?

132
00:05:54,410 --> 00:05:57,560
บวก 14 หารด้วย 0 2 7

133
00:05:57,560 --> 00:05:59,280
15 สิ่งที่เรากำลังมองหา?

134
00:05:59,280 --> 00:05:59,780
เลขที่

135
00:05:59,780 --> 00:06:02,930
มันใกล้สวย แต่เรากำลังมองหา
สำหรับค่าใหญ่กว่าเล็กน้อยว่า

136
00:06:02,930 --> 00:06:06,310
>> ดังนั้นเรารู้ว่ามันเป็นไปได้
จะไม่มีที่ไหนเลยที่ด้านซ้ายของ 15

137
00:06:06,310 --> 00:06:08,540
เป้าหมายมากกว่า
สิ่งที่อยู่ในจุดกึ่งกลาง

138
00:06:08,540 --> 00:06:12,450
และเพื่อให้เรากำหนดจุดเริ่มต้นใหม่ที่จะ
เป็นเพียงแค่ไปทางขวาของกลาง

139
00:06:12,450 --> 00:06:16,130
จุดกึ่งกลางในปัจจุบันคือ 7 ดังนั้น
สมมติว่าจุดเริ่มต้นใหม่คือ 8

140
00:06:16,130 --> 00:06:18,130
และสิ่งที่เราได้อย่างมีประสิทธิภาพ
ทำอีกครั้งจะถูกละเว้น

141
00:06:18,130 --> 00:06:21,150
ครึ่งซ้ายทั้งหมดของอาร์เรย์

142
00:06:21,150 --> 00:06:23,750
>> ตอนนี้เราทำซ้ำ
ดำเนินการอย่างใดอย่างหนึ่งเวลามากขึ้น

143
00:06:23,750 --> 00:06:24,910
คำนวณจุดกึ่งกลางใหม่

144
00:06:24,910 --> 00:06:29,350
บวก 8 14 22 หารด้วย 2 11

145
00:06:29,350 --> 00:06:31,060
23 สิ่งที่เรากำลังมองหา?

146
00:06:31,060 --> 00:06:31,870
แต่น่าเสียดายที่ไม่มี

147
00:06:31,870 --> 00:06:34,930
เรากำลังมองหาค่า
ที่น้อยกว่า 23

148
00:06:34,930 --> 00:06:37,850
และดังนั้นในกรณีนี้เราจะ
ที่จะเปลี่ยนจุดสิ้นสุดจะเป็นเพียง

149
00:06:37,850 --> 00:06:40,035
ที่ด้านซ้ายของจุดกึ่งกลางในปัจจุบัน

150
00:06:40,035 --> 00:06:43,440
จุดกึ่งกลางในปัจจุบันคือ 11 และ
ดังนั้นเราจะตั้งจุดสิ้นสุดใหม่

151
00:06:43,440 --> 00:06:46,980
สำหรับครั้งต่อไปที่เราจะไป
ผ่านขั้นตอนนี้ถึง 10

152
00:06:46,980 --> 00:06:48,660
>> อีกครั้งที่เราจะไปผ่านกระบวนการอีกครั้ง

153
00:06:48,660 --> 00:06:49,640
คำนวณจุดกึ่งกลาง

154
00:06:49,640 --> 00:06:53,100
8 บวก 10 หารด้วย 2 คือ 9

155
00:06:53,100 --> 00:06:54,750
19 สิ่งที่เรากำลังมองหา?

156
00:06:54,750 --> 00:06:55,500
แต่น่าเสียดายที่ไม่มี

157
00:06:55,500 --> 00:06:58,050
เรายังคงมองหา
จำนวนน้อยกว่า

158
00:06:58,050 --> 00:07:02,060
ดังนั้นเราจะเปลี่ยนจุดสิ้นสุดเวลานี้
จะเป็นเพียงทางด้านซ้ายของจุดกึ่งกลางที่

159
00:07:02,060 --> 00:07:05,532
จุดกึ่งกลางในขณะนี้ 9
ดังนั้นจุดสิ้นสุดจะ 8

160
00:07:05,532 --> 00:07:07,920
และตอนนี้เรากำลังเพียงแค่มอง
ที่อาร์เรย์องค์ประกอบหนึ่ง

161
00:07:07,920 --> 00:07:10,250
>> อะไรจุดกึ่งกลางของอาร์เรย์นี้หรือไม่?

162
00:07:10,250 --> 00:07:13,459
ดีก็เริ่มต้นที่ 8 มัน
สิ้นสุดที่ 8 จุดกึ่งกลางคือ 8

163
00:07:13,459 --> 00:07:14,750
นั่นคือสิ่งที่เรากำลังมองหา?

164
00:07:14,750 --> 00:07:16,339
เรากำลังมองหา 17

165
00:07:16,339 --> 00:07:17,380
ไม่มีเรากำลังมองหา 16

166
00:07:17,380 --> 00:07:20,160
ดังนั้นถ้ามันมีอยู่ในอาร์เรย์
มันต้องมีอยู่ที่ไหนสักแห่ง

167
00:07:20,160 --> 00:07:21,935
ด้านซ้ายของที่เรามีอยู่ในปัจจุบัน

168
00:07:21,935 --> 00:07:23,060
ดังนั้นสิ่งที่เราจะทำอย่างไร

169
00:07:23,060 --> 00:07:26,610
ดีที่เราจะตั้งจุดสิ้นสุดจะเป็นเพียง
ที่ด้านซ้ายของจุดกึ่งกลางในปัจจุบัน

170
00:07:26,610 --> 00:07:29,055
ดังนั้นเราจะเปลี่ยนจุดสิ้นสุด 7

171
00:07:29,055 --> 00:07:32,120
คุณเห็นสิ่งที่เพิ่ง
เกิดขึ้นที่นี่ แต่?

172
00:07:32,120 --> 00:07:33,370
เงยหน้าขึ้นมองที่นี่ตอนนี้

173
00:07:33,370 --> 00:07:35,970
>> เริ่มต้นอยู่ในขณะนี้สูงกว่าปลาย

174
00:07:35,970 --> 00:07:39,620
ได้อย่างมีประสิทธิภาพปลายทั้งสองข้าง
ของอาร์เรย์ของเราได้ข้าม

175
00:07:39,620 --> 00:07:42,252
และเป็นจุดเริ่มต้นคือ
ขณะนี้หลังจากจุดสิ้นสุด

176
00:07:42,252 --> 00:07:43,960
ดีที่ไม่ได้
ทำให้รู้สึกใด ๆ ใช่มั้ย?

177
00:07:43,960 --> 00:07:47,960
ดังนั้นตอนนี้สิ่งที่เราสามารถพูดได้ก็คือเรา
มีอาร์เรย์ย่อยขนาด 0

178
00:07:47,960 --> 00:07:50,110
และเมื่อเรากำลังอากาศ
จุดนี้ที่เราสามารถทำได้ในขณะนี้

179
00:07:50,110 --> 00:07:53,940
รับประกันองค์ประกอบที่ 16
ไม่อยู่ในอาร์เรย์

180
00:07:53,940 --> 00:07:56,280
เพราะจุดเริ่มต้น
และจุดสิ้นสุดได้ข้าม

181
00:07:56,280 --> 00:07:58,340
และดังนั้นจึงไม่ได้มี

182
00:07:58,340 --> 00:08:01,340
ตอนนี้สังเกตเห็นว่านี้เป็นเพียงเล็กน้อย
แตกต่างจากจุดเริ่มต้นและสิ้นสุด

183
00:08:01,340 --> 00:08:02,900
ชี้เป็นเหมือนกัน

184
00:08:02,900 --> 00:08:05,030
ถ้าเราได้รับการมอง
17 ก็จะมี

185
00:08:05,030 --> 00:08:08,870
รับในอาร์เรย์และเป็นจุดเริ่มต้น
และจุดสิ้นสุดของการทำซ้ำที่ผ่านมา

186
00:08:08,870 --> 00:08:11,820
ก่อนที่จะจุดเหล่านั้นข้าม
เราจะได้พบมี 17

187
00:08:11,820 --> 00:08:15,510
ก็ต่อเมื่อพวกเขาข้ามที่เราสามารถทำได้
รับประกันได้ว่าองค์ประกอบไม่ได้

188
00:08:15,510 --> 00:08:17,180
อยู่ในอาร์เรย์

189
00:08:17,180 --> 00:08:20,260
>> ดังนั้นขอให้ใช้เวลามากน้อย
ขั้นตอนกว่าการค้นหาเชิงเส้น

190
00:08:20,260 --> 00:08:23,250
ในสถานการณ์ที่เลวร้ายที่สุดกรณีที่เรามี
การแยกรายชื่อขององค์ประกอบ n

191
00:08:23,250 --> 00:08:27,770
ซ้ำแล้วซ้ำอีกในช่วงครึ่งปีที่จะหาเป้าหมาย
เพราะองค์ประกอบเป้าหมาย

192
00:08:27,770 --> 00:08:33,110
จะเป็นหนึ่งในที่ผ่านมา
หารหรือมันไม่ได้อยู่ที่ทุกคน

193
00:08:33,110 --> 00:08:37,830
ดังนั้นในกรณีที่เลวร้ายที่สุดที่เราต้อง
แยก array-- ที่คุณรู้หรือไม่?

194
00:08:37,830 --> 00:08:40,510
เข้าสู่ระบบครั้ง n; เรา
ต้องตัดปัญหา

195
00:08:40,510 --> 00:08:42,610
ในช่วงครึ่งปีจำนวนหนึ่งครั้ง

196
00:08:42,610 --> 00:08:45,160
จำนวนครั้งนั่นคือ n ล็อก

197
00:08:45,160 --> 00:08:46,510
>> สถานการณ์กรณีที่ดีที่สุดคืออะไร?

198
00:08:46,510 --> 00:08:48,899
ดีครั้งแรกที่เรา
คำนวณจุดกึ่งกลาง,

199
00:08:48,899 --> 00:08:50,190
เราพบว่าสิ่งที่เรากำลังมองหา

200
00:08:50,190 --> 00:08:52,150
ในทุกที่แล้ว
ตัวอย่างในการค้นหาแบบไบนารี

201
00:08:52,150 --> 00:08:55,489
เราได้ไปเพียงกว่าถ้าเรามี
รับการมองหาองค์ประกอบที่ 15

202
00:08:55,489 --> 00:08:57,030
เราจะพบว่าการได้ทันที

203
00:08:57,030 --> 00:08:58,321
นั่นคือที่จุดเริ่มต้น

204
00:08:58,321 --> 00:09:01,200
นั่นคือจุดกึ่งกลางของ
ความพยายามครั้งแรกที่แยก

205
00:09:01,200 --> 00:09:03,950
ส่วนในการค้นหาไบนารี

206
00:09:03,950 --> 00:09:06,350
>> และในที่เลวร้ายที่สุด
กรณีการค้นหาแบบไบนารีทำงาน

207
00:09:06,350 --> 00:09:11,580
n ในการเข้าสู่ระบบที่ดีขึ้นเป็นอย่างมาก
กว่าการค้นหาเชิงเส้นในกรณีที่เลวร้ายที่สุด

208
00:09:11,580 --> 00:09:16,210
ในกรณีที่ดีที่สุดไบนารี
ค้นหาทำงานในโอเมก้า 1

209
00:09:16,210 --> 00:09:18,990
ดังนั้นการค้นหาแบบไบนารีเป็นจำนวนมาก
ดีกว่าการค้นหาเชิงเส้น

210
00:09:18,990 --> 00:09:23,270
แต่คุณต้องจัดการกับกระบวนการของ
การเรียงลำดับอาร์เรย์ของคุณก่อนที่คุณสามารถ

211
00:09:23,270 --> 00:09:26,140
ใช้ประโยชน์จากพลังของการค้นหาไบนารี

212
00:09:26,140 --> 00:09:27,130
>> ฉันลอยด์ดั๊ก

213
00:09:27,130 --> 00:09:29,470
นี่คือซี 50

214
00:09:29,470 --> 00:09:31,070