1
00:00:00,000 --> 00:00:13,300

2
00:00:13,300 --> 00:00:15,010
>> ROB สลิง: สวัสดีครับผมร็อบ

3
00:00:15,010 --> 00:00:16,790
เราจะใช้ค้นหาแบบไบนารีได้อย่างไร

4
00:00:16,790 --> 00:00:18,770
ลองหา

5
00:00:18,770 --> 00:00:23,400
ดังนั้นโปรดทราบว่าการค้นหานี้เรากำลังจะ
ในการดำเนินการซ้ำ

6
00:00:23,400 --> 00:00:27,470
นอกจากนี้คุณยังสามารถใช้ค้นหาแบบไบนารี
ซ้ำดังนั้นหากคุณไม่ว่า

7
00:00:27,470 --> 00:00:29,280
ที่ดีอย่างสมบูรณ์แบบ

8
00:00:29,280 --> 00:00:32,820
>> ตอนแรกให้จำสิ่งที่
พารามิเตอร์เพื่อค้นหาจะหมายถึงการเป็น

9
00:00:32,820 --> 00:00:36,120
ที่นี่เราเห็นคุณค่า int ซึ่งเป็น
ควรจะเป็นค่าผู้ใช้

10
00:00:36,120 --> 00:00:37,320
ค้นหา

11
00:00:37,320 --> 00:00:40,800
เราจะเห็นอาร์เรย์ค่า int ซึ่ง
เป็นอาร์เรย์ที่เรากำลัง

12
00:00:40,800 --> 00:00:42,520
หาค่า

13
00:00:42,520 --> 00:00:45,602
และเราจะเห็น int n ซึ่งคือ
ความยาวของอาร์เรย์ของเรา

14
00:00:45,602 --> 00:00:47,410
>> ตอนนี้สิ่งแรกที่แรก

15
00:00:47,410 --> 00:00:51,350
เราตรวจสอบเพื่อดูว่า n เท่ากับ 0 ใน
ซึ่งในกรณีที่เรากลับเท็จ

16
00:00:51,350 --> 00:00:54,770
นั่นคือคำพูดว่าถ้าเรามีที่ว่าง
อาร์เรย์ค่าเป็นอย่างชัดเจนไม่ได้อยู่ใน

17
00:00:54,770 --> 00:00:57,860
แถวที่ว่างเปล่าเพื่อให้เราสามารถกลับเท็จ

18
00:00:57,860 --> 00:01:01,250
>> ตอนนี้เราต้องการทำจริงไบนารี
เป็นส่วนหนึ่งของการค้นหาค้นหาแบบไบนารี

19
00:01:01,250 --> 00:01:04,780
ดังนั้นเราจึงต้องการที่จะหาตรงกลาง
องค์ประกอบของอาร์เรย์นี้

20
00:01:04,780 --> 00:01:09,130
ที่นี่เราพูดกลางเท่ากับ n แบ่ง
2 เนื่องจากองค์ประกอบตรงกลางเป็น

21
00:01:09,130 --> 00:01:12,240
จะเป็นความยาวของ
อาเรย์ของเราหารด้วย 2

22
00:01:12,240 --> 00:01:15,040
ตอนนี้เรากำลังจะตรวจสอบเพื่อดูว่า
องค์ประกอบกลางเท่ากับค่าที่เรากำลัง

23
00:01:15,040 --> 00:01:16,160
ค้นหา

24
00:01:16,160 --> 00:01:21,030
ดังนั้นหากค่ากลางเท่ากับค่าเรา
สามารถกลับจริงตั้งแต่ที่เราพบ

25
00:01:21,030 --> 00:01:22,810
ค่าในอาเรย์ของเรา

26
00:01:22,810 --> 00:01:26,380
>> แต่ถ้าที่ไม่เป็นความจริงตอนนี้
ที่เราต้องทำซ้ำ

27
00:01:26,380 --> 00:01:27,840
ขั้นตอนของการค้นหาแบบไบนารี

28
00:01:27,840 --> 00:01:30,450
เราจำเป็นต้องค้นหาอย่างใดอย่างหนึ่งที่จะ
ด้านซ้ายของแถวหรือ

29
00:01:30,450 --> 00:01:32,320
ตรงกลางของแถว

30
00:01:32,320 --> 00:01:39,280
ดังนั้นที่นี่เราบอกว่าถ้าค่าที่ตรงกลางเป็น
น้อยกว่าค่าที่หมายถึงค่าที่

31
00:01:39,280 --> 00:01:41,350
มากกว่าตรงกลาง
ของอาร์เรย์

32
00:01:41,350 --> 00:01:45,790
ดังนั้นจะต้องมีค่าทางด้านขวาของ
องค์ประกอบที่เราก็มองไปที่

33
00:01:45,790 --> 00:01:48,090
>> ดังนั้นที่นี่เรากำลังจะ
ค้นหาซ้ำ

34
00:01:48,090 --> 00:01:50,320
และเราจะดูที่สิ่งที่เรากำลังผ่าน
นี้ในครั้งที่สอง

35
00:01:50,320 --> 00:01:53,440
แต่เรากำลังจะค้นหาเพื่อ
ที่เหมาะสมขององค์ประกอบกลาง

36
00:01:53,440 --> 00:01:57,710
และในกรณีอื่น ๆ ที่หมายความว่า
ค่าน้อยกว่าตรงกลางของ

37
00:01:57,710 --> 00:02:00,660
อาเรย์และอื่น ๆ ที่เรากำลังจะ
เพื่อค้นหาทางด้านซ้าย

38
00:02:00,660 --> 00:02:03,520
ตอนนี้ด้านซ้ายเป็นไปได้
บิตง่ายต่อการมองไปที่

39
00:02:03,520 --> 00:02:07,770
ดังนั้นเราเห็นที่นี่ว่าเราซ้ำ
ค้นหาเรียกครั้งแรกที่

40
00:02:07,770 --> 00:02:10,120
อาร์กิวเมนต์เป็นอีกครั้งค่า
เรากำลังมองหาในช่วง

41
00:02:10,120 --> 00:02:14,970
อาร์กิวเมนต์ที่สองเป็นไปได้
อาร์เรย์ที่เราค้นหาผ่าน

42
00:02:14,970 --> 00:02:17,090
และองค์ประกอบสุดท้ายในขณะนี้คือตรงกลาง

43
00:02:17,090 --> 00:02:21,650
โปรดจำไว้ว่าพารามิเตอร์สุดท้ายคือ int ของเรา
n เพื่อให้เป็นความยาวของอาร์เรย์ของเรา

44
00:02:21,650 --> 00:02:25,310
>> ในการเรียกร้องซ้ำในการค้นหาเรา
บอกว่าตอนนี้ความยาวของ

45
00:02:25,310 --> 00:02:27,230
แถวกลาง

46
00:02:27,230 --> 00:02:32,900
ดังนั้นถ้าอาร์เรย์ของเราคือขนาด 20 และเรา
ค้นหาที่ดัชนี 10 ตั้งแต่กลางเป็น

47
00:02:32,900 --> 00:02:36,930
20 หารด้วย 2 นั่นหมายความว่าเรากำลัง
10 ผ่านใหม่

48
00:02:36,930 --> 00:02:38,300
ความยาวของอาร์เรย์ของเรา

49
00:02:38,300 --> 00:02:41,910
โปรดจำไว้ว่าเมื่อคุณมีอาร์เรย์
ความยาว 10 นั่นหมายความว่าถูกต้อง

50
00:02:41,910 --> 00:02:45,450
องค์ประกอบในดัชนี 0 ถึง 9

51
00:02:45,450 --> 00:02:50,120
ดังนั้นนี่คือสิ่งที่เราต้องการ
ระบุอาร์เรย์การปรับปรุงของเรา - ซ้าย

52
00:02:50,120 --> 00:02:53,010
อาร์เรย์จากองค์ประกอบกลาง

53
00:02:53,010 --> 00:02:55,710
>> ดังนั้นมองไปทางขวาเป็น
บิตยากขึ้น

54
00:02:55,710 --> 00:03:00,170
ตอนแรกให้พิจารณาระยะเวลา
ของอาร์เรย์ที่ด้านขวาของ

55
00:03:00,170 --> 00:03:01,240
องค์ประกอบกลาง

56
00:03:01,240 --> 00:03:08,390
ดังนั้นถ้าอาร์เรย์ของเราคือขนาด n แล้​​ว
แถวใหม่จะมีขนาด n ลบ

57
00:03:08,390 --> 00:03:10,140
กลางลบ 1

58
00:03:10,140 --> 00:03:12,530
ดังนั้นขอคิด n ลบกลาง

59
00:03:12,530 --> 00:03:18,710
>> อีกครั้งถ้าอาร์เรย์มีขนาด 20 และ
เราหารด้วย 2 จะได้รับตรงกลาง

60
00:03:18,710 --> 00:03:23,540
เพื่อให้ตรงกลางเป็น 10 แล้ว n ลบกลาง
เป็นไปเพื่อให้เรามี 10 ดังนั้น 10

61
00:03:23,540 --> 00:03:25,330
องค์ประกอบทางด้านขวาของกลาง

62
00:03:25,330 --> 00:03:27,780
แต่เรายังมีลบนี้
1 เนื่องจากเราไม่ต้องการที่จะ

63
00:03:27,780 --> 00:03:29,700
รวมถึงตัวเองกลาง

64
00:03:29,700 --> 00:03:34,190
ดังนั้น n ลบลบ 1 ตรงกลางจะช่วยให้เรา
จำนวนรวมขององค์ประกอบทางด้านขวา

65
00:03:34,190 --> 00:03:36,800
ของดัชนีกลางในอาร์เรย์

66
00:03:36,800 --> 00:03:41,870
>> ตอนนี้ที่นี่จำไว้ว่ากลาง
พารามิเตอร์เป็นอาร์เรย์ค่า

67
00:03:41,870 --> 00:03:46,180
ดังนั้นที่นี่เรากำลังผ่าน
การปรับปรุงค่าอาร์เรย์

68
00:03:46,180 --> 00:03:50,930
ค่านี้บวกกลางบวก 1
จริงว่าเรียกซ้ำ

69
00:03:50,930 --> 00:03:56,460
ค้นหาผ่านในอาร์เรย์ใหม่ที่
ที่แถวใหม่จะเริ่มต้นในช่วงกลาง

70
00:03:56,460 --> 00:03:59,370
บวกหนึ่งของอาร์เรย์ค่านิยมของเราที่เป็นต้นฉบับ

71
00:03:59,370 --> 00:04:05,400
>> ไวยากรณ์สำรองสำหรับว่าตอนนี้ที่
คุณได้เริ่มต้นที่จะเห็นตัวชี้เป็น

72
00:04:05,400 --> 00:04:10,170
ค่ากลางเครื่องหมายบวก 1

73
00:04:10,170 --> 00:04:17,149
ดังนั้นคว้าที่อยู่ตรงกลางของ
บวกองค์ประกอบหนึ่งของค่า

74
00:04:17,149 --> 00:04:23,690
>> ตอนนี้ถ้าคุณไม่สบาย
การปรับเปลี่ยนอาร์เรย์ที่ชอบคุณ

75
00:04:23,690 --> 00:04:28,900
นอกจากนี้ยังอาจมีการดำเนินการโดยใช้
ฟังก์ชั่นช่วยซ้ำที่

76
00:04:28,900 --> 00:04:31,680
ฟังก์ชั่นที่จะช่วย
การขัดแย้งมากขึ้น

77
00:04:31,680 --> 00:04:36,610
ดังนั้นแทนการเพียงแค่ค่า
อาเรย์และขนาดของอาร์เรย์

78
00:04:36,610 --> 00:04:42,315
ฟังก์ชั่นผู้ช่วยอาจจะใช้เวลามากขึ้น
ขัดแย้งรวมทั้งดัชนีที่ต่ำกว่า

79
00:04:42,315 --> 00:04:45,280
ที่คุณจะดูแลเกี่ยวกับในอาร์เรย์
และดัชนีบนที่คุณสนใจ

80
00:04:45,280 --> 00:04:46,300
เกี่ยวกับอาเรย์

81
00:04:46,300 --> 00:04:49,770
>> และเพื่อให้การติดตามของทั้งสองที่ต่ำกว่า
ดัชนีและดัชนีบนที่คุณทำไม่ได้

82
00:04:49,770 --> 00:04:52,780
ต้องเคยแก้ไข
อาร์เรย์ค่าเดิม

83
00:04:52,780 --> 00:04:56,390
คุณก็สามารถดำเนินการต่อไป
ใช้อาร์เรย์ค่า

84
00:04:56,390 --> 00:04:59,540
แต่ที่นี่สังเกตเห็นเราไม่จำเป็นต้องช่วย
ทำงานตราบใดที่เรา

85
00:04:59,540 --> 00:05:01,760
ยินดีที่จะปรับเปลี่ยนเดิม
อาร์เรย์ค่า

86
00:05:01,760 --> 00:05:05,020
เรายินดีที่จะผ่านใน
ค่าปรับปรุง

87
00:05:05,020 --> 00:05:09,140
>> ตอนนี้เราไม่สามารถค้นหา binary กว่า
อาเรย์ที่ไม่ได้คัดแยก

88
00:05:09,140 --> 00:05:12,220
ดังนั้นขอได้รับนี้แยกออก

89
00:05:12,220 --> 00:05:17,650
ตอนนี้สังเกตเห็นการจัดเรียงที่ผ่านมาสอง
int ค่าพารามิเตอร์ซึ่งเป็น

90
00:05:17,650 --> 00:05:21,110
อาร์เรย์ที่เรากำลังเรียงลำดับและ int n,
ซึ่งเป็นความยาวของแถวที่

91
00:05:21,110 --> 00:05:22,250
เรากำลังการเรียงลำดับ

92
00:05:22,250 --> 00:05:24,840
ดังนั้นที่นี่เราต้องการที่จะใช้
ขั้นตอนวิธีการเรียงลำดับ

93
00:05:24,840 --> 00:05:26,690
ที่เป็นของ n o ยกกำลัง

94
00:05:26,690 --> 00:05:30,560
คุณสามารถเลือกเรียงลำดับฟองเลือก
เรียงลำดับหรือการจัดเรียงแทรกหรือ

95
00:05:30,560 --> 00:05:32,670
บางประเภทอื่น ๆ ที่เรายังไม่ได้
ที่เห็นในชั้นเรียน

96
00:05:32,670 --> 00:05:36,380
แต่ที่นี่เราจะ
การเลือกใช้ประเภท

97
00:05:36,380 --> 00:05:40,030
>> ดังนั้นเรากำลังจะย้ำ
ช่วงอาร์เรย์ทั้งหมด

98
00:05:40,030 --> 00:05:44,360
ดีที่นี่เราจะเห็นว่าเรากำลัง iterating
จาก 0 ถึง n ลบ 1

99
00:05:44,360 --> 00:05:45,990
ทำไมไม่ไปตลอดทางถึง n?

100
00:05:45,990 --> 00:05:49,320
ดีถ้าเราได้เรียงลำดับแล้วเป็นครั้งแรก
n ลบ 1 องค์ประกอบแล้ว

101
00:05:49,320 --> 00:05:54,420
องค์ประกอบสุดท้ายมากแล้วสิ่งที่จะต้อง
ในสถานที่ที่ถูกต้องเพื่อให้การเรียงลำดับไป

102
00:05:54,420 --> 00:05:56,520
อาร์เรย์ทั้งหมด

103
00:05:56,520 --> 00:05:58,770
>> ตอนนี้จำได้ว่าการเลือก
ผลงานการจัดเรียง

104
00:05:58,770 --> 00:06:01,950
เรากำลังจะไปกว่าอาร์เรย์ทั้งหมด
มองหาค่าต่ำสุดใน

105
00:06:01,950 --> 00:06:04,480
อาร์เรย์และติดที่
ในขั้นต้น

106
00:06:04,480 --> 00:06:07,610
จากนั้นเราจะไปกว่าทั้ง
อาเรย์อีกครั้งมองหาที่สอง

107
00:06:07,610 --> 00:06:10,410
องค์ประกอบที่เล็กที่สุดและติดที่
อยู่ในตำแหน่งที่สองใน

108
00:06:10,410 --> 00:06:12,100
อาเรย์และอื่น ๆ

109
00:06:12,100 --> 00:06:14,330
ดังนั้นนั่นคือสิ่งที่จะทำนี้

110
00:06:14,330 --> 00:06:17,290
>> ที่นี่เราจะเห็นว่าเรา
การตั้งค่าขั้นต่ำในปัจจุบัน

111
00:06:17,290 --> 00:06:20,030
ค่าดัชนีลำดับที่ i

112
00:06:20,030 --> 00:06:23,160
ดังนั้นในการทำซ้ำเป็นครั้งแรกที่เรากำลังจะ
ที่จะต้องพิจารณาค่าต่ำสุดจะเป็น

113
00:06:23,160 --> 00:06:25,030
จุดเริ่มต้นของอาเรย์ของเรา

114
00:06:25,030 --> 00:06:28,500
จากนั้นเราจะย้ำกว่า
ส่วนที่เหลือของอาร์เรย์, การตรวจสอบเพื่อ

115
00:06:28,500 --> 00:06:31,870
ดูว่ามีองค์ประกอบใด ๆ ที่มีขนาดเล็กกว่า
อย่างใดอย่างหนึ่งที่เรากำลัง

116
00:06:31,870 --> 00:06:33,900
พิจารณาขั้นต่ำ

117
00:06:33,900 --> 00:06:38,840
>> ดังนั้นที่นี่ค่าเจบวกหนึ่ง - ที่
น้อยกว่าสิ่งที่เรามีอยู่ในปัจจุบัน

118
00:06:38,840 --> 00:06:40,380
พิจารณาขั้นต่ำ

119
00:06:40,380 --> 00:06:42,940
แล้วเรากำลังจะปรับปรุงสิ่งที่
เราคิดว่าเป็นขั้นต่ำที่

120
00:06:42,940 --> 00:06:44,640
ดัชนีเจบวก 1

121
00:06:44,640 --> 00:06:48,540
ดังนั้นทำอย่างไรที่ทั่วอาร์เรย์ทั้งหมด
และหลังจากนี้สำหรับวงต่ำสุด

122
00:06:48,540 --> 00:06:53,160
ควรจะเป็นองค์ประกอบขั้นต่ำจาก
ตำแหน่งลำดับที่ i ในอาร์เรย์

123
00:06:53,160 --> 00:06:57,350
>> เมื่อเรามีที่เราสามารถสลับ
ค่าต่ำสุดในตำแหน่งลำดับที่ i

124
00:06:57,350 --> 00:06:58,230
ในอาร์เรย์

125
00:06:58,230 --> 00:07:00,130
ดังนั้นนี้เป็นเพียงการแลกเปลี่ยนมาตรฐาน

126
00:07:00,130 --> 00:07:03,940
เราเก็บไว้ในค่าชั่วคราว -
ค่าลำดับที่ i ในอาร์เรย์ -

127
00:07:03,940 --> 00:07:08,460
ใส่ลงไปในค่าลำดับที่ i ในอาร์เรย์
ค่าต่ำสุดที่เป็นมี

128
00:07:08,460 --> 00:07:13,580
แล้วเก็บกลับเข้ามาในที่
ค่าต่ำสุดในปัจจุบันที่ใช้จะเป็น

129
00:07:13,580 --> 00:07:16,460
ค่า i th-ในอาร์เรย์ดังนั้น
ว่าเราไม่ได้สูญเสียมันไป

130
00:07:16,460 --> 00:07:20,510
>> ดังนั้นที่ยังคงอยู่กับ
ซ้ำไป

131
00:07:20,510 --> 00:07:23,480
เราจะเริ่มมองหาที่สอง
ค่าต่ำสุดและใส่ที่เป็น

132
00:07:23,480 --> 00:07:24,590
ตำแหน่งที่สอง

133
00:07:24,590 --> 00:07:27,440
ซ้ำสามเราจะมองหา
ค่าต่ำสุดที่สามและแทรก

134
00:07:27,440 --> 00:07:31,550
ที่เป็นตำแหน่งที่สามและอื่น
จนกระทั่งเรามีอาร์เรย์ที่เรียงลำดับ

135
00:07:31,550 --> 00:07:33,820
ชื่อของฉันคือร็อบและ
เป็นประเภทที่เลือก

136
00:07:33,820 --> 00:07:39,456