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

2
00:00:13,300 --> 00:00:15,010
>> ROB Bowden: Xin chào, tôi Rob.

3
00:00:15,010 --> 00:00:16,790
Làm thế nào để chúng tôi sử dụng tìm kiếm nhị phân?

4
00:00:16,790 --> 00:00:18,770
Hãy tìm hiểu.

5
00:00:18,770 --> 00:00:23,400
Vì vậy, lưu ý rằng tìm kiếm này chúng ta sẽ
thực hiện đệ quy.

6
00:00:23,400 --> 00:00:27,470
Bạn cũng có thể thực hiện tìm kiếm nhị phân
lặp đi lặp lại, vì vậy nếu bạn đã làm điều đó,

7
00:00:27,470 --> 00:00:29,280
đó là hoàn toàn tốt đẹp.

8
00:00:29,280 --> 00:00:32,820
>> Bây giờ đầu tiên, chúng ta hãy nhớ những gì
các thông số để tìm kiếm được có nghĩa là phải.

9
00:00:32,820 --> 00:00:36,120
Ở đây, chúng ta thấy giá trị int, đó là
nghĩa vụ phải được các giá trị người dùng

10
00:00:36,120 --> 00:00:37,320
tìm kiếm.

11
00:00:37,320 --> 00:00:40,800
Chúng ta thấy các mảng int giá trị, mà
là mảng mà chúng ta đang

12
00:00:40,800 --> 00:00:42,520
tìm kiếm giá trị.

13
00:00:42,520 --> 00:00:45,602
Và chúng ta thấy int n, đó là
chiều dài của mảng của chúng tôi.

14
00:00:45,602 --> 00:00:47,410
>> Bây giờ, điều đầu tiên đầu tiên.

15
00:00:47,410 --> 00:00:51,350
Chúng tôi kiểm tra xem nếu n bằng 0, trong
trường hợp mà chúng tôi trả về false.

16
00:00:51,350 --> 00:00:54,770
Đó chỉ nói rằng nếu chúng ta có một sản phẩm nào
mảng, giá trị rõ ràng là không trong một

17
00:00:54,770 --> 00:00:57,860
mảng sản phẩm nào, vì vậy chúng tôi có thể trả về false.

18
00:00:57,860 --> 00:01:01,250
>> Bây giờ, chúng tôi thực sự muốn làm nhị phân
phần tìm kiếm của tìm kiếm nhị phân.

19
00:01:01,250 --> 00:01:04,780
Vì vậy, chúng tôi muốn tìm giữa
phần tử của mảng này.

20
00:01:04,780 --> 00:01:09,130
Ở đây, chúng ta nói giữa bằng n chia
2, vì các yếu tố trung là

21
00:01:09,130 --> 00:01:12,240
sẽ được chiều dài của
mảng của chúng tôi chia cho 2.

22
00:01:12,240 --> 00:01:15,040
Bây giờ chúng ta sẽ kiểm tra xem nếu
yếu tố trung bằng giá trị chúng tôi

23
00:01:15,040 --> 00:01:16,160
tìm kiếm.

24
00:01:16,160 --> 00:01:21,030
Vì vậy, nếu giá trị trung bằng giá trị, chúng tôi
có thể trở lại đúng kể từ khi chúng tôi tìm thấy

25
00:01:21,030 --> 00:01:22,810
giá trị trong mảng của chúng tôi.

26
00:01:22,810 --> 00:01:26,380
>> Nhưng nếu đó là không đúng sự thật, bây giờ
chúng ta cần phải làm đệ quy

27
00:01:26,380 --> 00:01:27,840
bước của tìm kiếm nhị phân.

28
00:01:27,840 --> 00:01:30,450
Chúng tôi cần phải tìm kiếm hoặc đến
trái của mảng hoặc các

29
00:01:30,450 --> 00:01:32,320
giữa mảng.

30
00:01:32,320 --> 00:01:39,280
Vì vậy, ở đây, chúng ta nói nếu giá trị ở giữa là
thấp hơn giá trị, có nghĩa là giá trị mà

31
00:01:39,280 --> 00:01:41,350
lớn hơn giữa
của mảng.

32
00:01:41,350 --> 00:01:45,790
Vì vậy, giá trị phải là ở bên phải của
yếu tố mà chúng ta chỉ nhìn vào.

33
00:01:45,790 --> 00:01:48,090
>> Vì vậy, ở đây, chúng ta sẽ
tìm kiếm đệ quy.

34
00:01:48,090 --> 00:01:50,320
Và chúng tôi sẽ nhìn vào những gì chúng tôi đang đi qua
với điều này trong một giây.

35
00:01:50,320 --> 00:01:53,440
Nhưng chúng ta sẽ tìm đến
bên phải của phần trung lưu.

36
00:01:53,440 --> 00:01:57,710
Và trong trường hợp khác, có nghĩa là
giá trị thấp hơn giữa

37
00:01:57,710 --> 00:02:00,660
mảng, và do đó chúng ta sẽ
để tìm kiếm bên trái.

38
00:02:00,660 --> 00:02:03,520
Bây giờ, bên trái là có được
một chút dễ dàng hơn để xem xét.

39
00:02:03,520 --> 00:02:07,770
Vì vậy, chúng ta thấy ở đây là chúng ta đệ quy
kêu gọi tìm kiếm nơi đầu tiên

40
00:02:07,770 --> 00:02:10,120
đối số là, một lần nữa, giá trị
chúng tôi đang tìm kiếm hơn.

41
00:02:10,120 --> 00:02:14,970
Đối số thứ hai là có được các
mảng mà chúng tôi đã tìm kiếm trên.

42
00:02:14,970 --> 00:02:17,090
Và yếu tố cuối cùng bây giờ là giữa.

43
00:02:17,090 --> 00:02:21,650
Hãy nhớ rằng các tham số cuối cùng là int của chúng tôi
n, vì vậy đó là chiều dài của mảng của chúng tôi.

44
00:02:21,650 --> 00:02:25,310
>> Trong các cuộc gọi đệ quy để tìm kiếm, chúng tôi
bây giờ nói rằng chiều dài của

45
00:02:25,310 --> 00:02:27,230
mảng là trung.

46
00:02:27,230 --> 00:02:32,900
Vì vậy, nếu mảng của chúng tôi là các kích thước 20 và chúng tôi
tìm kiếm ở chỉ số 10, từ giữa là

47
00:02:32,900 --> 00:02:36,930
20 chia cho 2, có nghĩa là chúng tôi
đi qua 10 như mới

48
00:02:36,930 --> 00:02:38,300
chiều dài của mảng của chúng tôi.

49
00:02:38,300 --> 00:02:41,910
Hãy nhớ rằng khi bạn có một mảng
chiều dài 10, có nghĩa là hợp lệ

50
00:02:41,910 --> 00:02:45,450
yếu tố nằm trong các chỉ số từ 0 đến 9.

51
00:02:45,450 --> 00:02:50,120
Vì vậy, đây là chính xác những gì chúng tôi muốn
chỉ định mảng cập nhật của chúng tôi - bên trái

52
00:02:50,120 --> 00:02:53,010
mảng từ các yếu tố trung.

53
00:02:53,010 --> 00:02:55,710
>> Vì vậy, nhìn bên phải là
một chút khó khăn hơn.

54
00:02:55,710 --> 00:03:00,170
Bây giờ đầu tiên, chúng ta hãy xem xét độ dài
của mảng bên phải của

55
00:03:00,170 --> 00:03:01,240
yếu tố trung.

56
00:03:01,240 --> 00:03:08,390
Vì vậy, nếu mảng của chúng tôi là kích thước n, thì
mảng mới sẽ có kích thước n trừ đi

57
00:03:08,390 --> 00:03:10,140
trừ giữa 1.

58
00:03:10,140 --> 00:03:12,530
Vì vậy, chúng ta hãy nghĩ n trừ đi giữa.

59
00:03:12,530 --> 00:03:18,710
>> Một lần nữa, nếu mảng đều có cỡ 20 và
chúng tôi chia cho 2 để có được giữa,

60
00:03:18,710 --> 00:03:23,540
nên giữa là 10, sau đó trừ đi n trung
sẽ cung cấp cho chúng tôi 10, vì vậy 10

61
00:03:23,540 --> 00:03:25,330
các yếu tố bên phải của trung.

62
00:03:25,330 --> 00:03:27,780
Nhưng chúng tôi cũng có trừ này
1, vì chúng ta không muốn

63
00:03:27,780 --> 00:03:29,700
bao gồm giữa chính nó.

64
00:03:29,700 --> 00:03:34,190
Vì vậy, trừ n trung trừ đi 1 cho chúng ta
tổng số của các yếu tố bên phải

65
00:03:34,190 --> 00:03:36,800
của chỉ số trung trong mảng.

66
00:03:36,800 --> 00:03:41,870
>> Bây giờ ở đây, hãy nhớ rằng giữa
tham số là mảng giá trị.

67
00:03:41,870 --> 00:03:46,180
Vì vậy, ở đây, chúng tôi đang đi qua một
cập nhật các giá trị mảng.

68
00:03:46,180 --> 00:03:50,930
Này các giá trị cộng thêm 1 trung là
thực sự nói đệ quy gọi

69
00:03:50,930 --> 00:03:56,460
tìm kiếm, đi qua trong một mảng mới, nơi
mà mảng mới bắt đầu ở giữa

70
00:03:56,460 --> 00:03:59,370
cộng với một trong những mảng giá trị ban đầu của chúng tôi.

71
00:03:59,370 --> 00:04:05,400
>> Một cú pháp thay thế cho rằng, bây giờ mà
bạn đã bắt đầu nhìn thấy con trỏ, là

72
00:04:05,400 --> 00:04:10,170
giá trị ký hiệu cộng với trung 1.

73
00:04:10,170 --> 00:04:17,149
Vì vậy, lấy địa chỉ của trung
cộng với một yếu tố của giá trị.

74
00:04:17,149 --> 00:04:23,690
>> Bây giờ, nếu bạn không thoải mái
sửa đổi một mảng như thế, bạn

75
00:04:23,690 --> 00:04:28,900
cũng có thể thực hiện điều này bằng cách sử dụng
một chức năng trợ giúp đệ quy, nơi

76
00:04:28,900 --> 00:04:31,680
mà có chức năng trợ giúp
nhiều đối số.

77
00:04:31,680 --> 00:04:36,610
Vì vậy, thay vì dùng chỉ giá trị,
mảng, và kích thước của mảng,

78
00:04:36,610 --> 00:04:42,315
các chức năng trợ giúp có thể mất nhiều hơn
lập luận, trong đó có chỉ số thấp hơn

79
00:04:42,315 --> 00:04:45,280
mà bạn sẽ quan tâm trong mảng
và chỉ số trên mà bạn quan tâm

80
00:04:45,280 --> 00:04:46,300
về mảng.

81
00:04:46,300 --> 00:04:49,770
>> Và do đó việc theo dõi của cả hai thấp hơn
chỉ số và chỉ số trên, bạn không

82
00:04:49,770 --> 00:04:52,780
cần phải bao giờ thay đổi
giá trị ban đầu mảng.

83
00:04:52,780 --> 00:04:56,390
Bạn chỉ có thể tiếp tục
sử dụng các mảng giá trị.

84
00:04:56,390 --> 00:04:59,540
Nhưng ở đây, nhận thấy chúng tôi không cần một người trợ giúp
chức năng miễn là chúng tôi

85
00:04:59,540 --> 00:05:01,760
sẵn sàng thay đổi bản gốc
giá trị mảng.

86
00:05:01,760 --> 00:05:05,020
Chúng tôi sẵn sàng để vượt qua trong
một cập nhật các giá trị.

87
00:05:05,020 --> 00:05:09,140
>> Bây giờ, chúng ta không thể tìm kiếm nhị phân trên
một mảng đó là phân loại.

88
00:05:09,140 --> 00:05:12,220
Vì vậy, chúng ta hãy sắp xếp này ra.

89
00:05:12,220 --> 00:05:17,650
Bây giờ, nhận thấy loại đó là quá khứ hai
thông số int giá trị, đó là

90
00:05:17,650 --> 00:05:21,110
mảng mà chúng ta đang phân loại, và int n,
đó là chiều dài của mảng mà

91
00:05:21,110 --> 00:05:22,250
chúng tôi đang phân loại.

92
00:05:22,250 --> 00:05:24,840
Vì vậy, ở đây chúng tôi muốn thực hiện
một thuật toán sắp xếp

93
00:05:24,840 --> 00:05:26,690
đó là o n bình phương.

94
00:05:26,690 --> 00:05:30,560
Bạn có thể chọn bong bóng sắp xếp, lựa chọn
sắp xếp, hoặc sắp xếp chèn, hoặc

95
00:05:30,560 --> 00:05:32,670
một số loại khác mà chúng tôi có không
thấy trong lớp.

96
00:05:32,670 --> 00:05:36,380
Nhưng ở đây, chúng ta sẽ
sử dụng lựa chọn sắp xếp.

97
00:05:36,380 --> 00:05:40,030
>> Vì vậy, chúng ta sẽ lặp
trên toàn bộ mảng.

98
00:05:40,030 --> 00:05:44,360
Vâng, ở đây chúng ta thấy rằng chúng ta đang lặp lại
từ 0 đến n trừ đi 1.

99
00:05:44,360 --> 00:05:45,990
Tại sao không phải tất cả các con đường lên đến n?

100
00:05:45,990 --> 00:05:49,320
Vâng, nếu chúng tôi đã sắp xếp đầu tiên
n trừ đi 1 yếu tố, sau đó các

101
00:05:49,320 --> 00:05:54,420
yếu tố cuối cùng những gì đã phải
trong địa điểm chính xác, vì vậy sắp xếp hơn

102
00:05:54,420 --> 00:05:56,520
toàn bộ mảng.

103
00:05:56,520 --> 00:05:58,770
>> Bây giờ, nhớ làm thế nào lựa chọn
loại hoạt động.

104
00:05:58,770 --> 00:06:01,950
Chúng ta sẽ đi qua toàn bộ mảng
tìm kiếm các giá trị tối thiểu trong

105
00:06:01,950 --> 00:06:04,480
mảng và cây gậy
lúc đầu.

106
00:06:04,480 --> 00:06:07,610
Sau đó chúng ta sẽ đi qua toàn bộ
mảng một lần nữa tìm kiếm thứ hai

107
00:06:07,610 --> 00:06:10,410
phần tử nhỏ nhất, và cây gậy
ở vị trí thứ hai trong

108
00:06:10,410 --> 00:06:12,100
mảng, và như vậy.

109
00:06:12,100 --> 00:06:14,330
Vì vậy, đó là những gì đang thực hiện.

110
00:06:14,330 --> 00:06:17,290
>> Ở đây, chúng ta đang thấy rằng chúng tôi
thiết lập tối thiểu hiện hành

111
00:06:17,290 --> 00:06:20,030
giá trị cho chỉ số thứ i.

112
00:06:20,030 --> 00:06:23,160
Vì vậy, trên phiên đầu tiên, chúng ta sẽ
xem xét các giá trị tối thiểu là

113
00:06:23,160 --> 00:06:25,030
sự bắt đầu của mảng của chúng tôi.

114
00:06:25,030 --> 00:06:28,500
Sau đó, chúng ta sẽ lặp qua
còn lại của mảng, kiểm tra để

115
00:06:28,500 --> 00:06:31,870
xem nếu có bất kỳ yếu tố nhỏ hơn
một trong đó chúng tôi hiện đang

116
00:06:31,870 --> 00:06:33,900
xem xét mức tối thiểu.

117
00:06:33,900 --> 00:06:38,840
>> Vì vậy, ở đây, giá trị j cộng với một - đó là
ít hơn những gì chúng tôi đang có

118
00:06:38,840 --> 00:06:40,380
xem xét mức tối thiểu.

119
00:06:40,380 --> 00:06:42,940
Sau đó chúng ta sẽ cập nhật những gì
chúng tôi nghĩ là tối thiểu để

120
00:06:42,940 --> 00:06:44,640
chỉ số j cộng với 1.

121
00:06:44,640 --> 00:06:48,540
Vì vậy, làm điều đó trên toàn bộ mảng,
và sau này cho vòng lặp, tối thiểu

122
00:06:48,540 --> 00:06:53,160
nên là yếu tố tối thiểu từ
vị trí thứ i trong mảng.

123
00:06:53,160 --> 00:06:57,350
>> Một khi chúng ta có điều đó, chúng ta có thể trao đổi các
giá trị tối thiểu vào vị trí thứ i

124
00:06:57,350 --> 00:06:58,230
trong mảng.

125
00:06:58,230 --> 00:07:00,130
Vì vậy, đây chỉ là một trao đổi tiêu chuẩn.

126
00:07:00,130 --> 00:07:03,940
Chúng tôi lưu trữ trong một giá trị tạm thời -
giá trị thứ i trong mảng -

127
00:07:03,940 --> 00:07:08,460
đưa vào giá trị thứ i trong mảng các
giá trị tối thiểu mà thuộc về ở đó,

128
00:07:08,460 --> 00:07:13,580
và sau đó lưu trữ trở lại nơi
giá trị tối thiểu hiện hành được sử dụng là

129
00:07:13,580 --> 00:07:16,460
giá trị thứ i trong mảng, vì vậy
rằng chúng tôi đã không mất nó.

130
00:07:16,460 --> 00:07:20,510
>> Vì vậy, mà vẫn tiếp tục trên
phiên bản kế tiếp.

131
00:07:20,510 --> 00:07:23,480
Chúng tôi sẽ bắt đầu tìm kiếm thứ hai
giá trị tối thiểu và chèn đó vào

132
00:07:23,480 --> 00:07:24,590
vị trí thứ hai.

133
00:07:24,590 --> 00:07:27,440
Trên lặp thứ ba, chúng tôi sẽ tìm kiếm
giá trị nhỏ nhất thứ ba và chèn

134
00:07:27,440 --> 00:07:31,550
đó vào vị trí thứ ba, và vì vậy
cho đến khi chúng tôi có một mảng được sắp xếp.

135
00:07:31,550 --> 00:07:33,820
Tên tôi là Rob, và điều này
là lựa chọn sắp xếp.

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