1
00:00:00,000 --> 00:00:03,346
>> [MUSIC CHƠI]

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

3
00:00:05,258 --> 00:00:06,220
>> DOUG LLOYD: Tất cả các quyền.

4
00:00:06,220 --> 00:00:08,140
Vì vậy, tìm kiếm nhị phân là một
thuật toán chúng ta có thể sử dụng

5
00:00:08,140 --> 00:00:10,530
để tìm một phần tử bên trong một mảng.

6
00:00:10,530 --> 00:00:14,710
Không giống như tìm kiếm tuyến tính, nó đòi hỏi một
điều kiện đặc biệt được đáp ứng trước,

7
00:00:14,710 --> 00:00:19,020
nhưng nó rất hiệu quả hơn nhiều nếu
mà điều kiện là, trong thực tế, đáp ứng.

8
00:00:19,020 --> 00:00:20,470
>> Vì vậy, ý tưởng ở đây là gì?

9
00:00:20,470 --> 00:00:21,780
đó là phân chia và chinh phục.

10
00:00:21,780 --> 00:00:25,100
Chúng tôi muốn giảm bớt kích thước của
khu vực tìm kiếm một nửa mỗi lần

11
00:00:25,100 --> 00:00:27,240
để tìm ra một số mục tiêu.

12
00:00:27,240 --> 00:00:29,520
Đây là nơi mà điều kiện
đến chơi, mặc dù.

13
00:00:29,520 --> 00:00:32,740
Chúng tôi chỉ có thể tận dụng sức mạnh của
loại bỏ một nửa của các yếu tố

14
00:00:32,740 --> 00:00:36,070
mà thậm chí không nhìn vào
họ nếu mảng được sắp xếp.

15
00:00:36,070 --> 00:00:39,200
>> Nếu đó là một hỗn hợp hoàn chỉnh lên,
chúng ta không thể chỉ ra khỏi bàn tay

16
00:00:39,200 --> 00:00:42,870
loại bỏ một nửa trong số các yếu tố, vì
chúng ta không biết những gì chúng ta vứt bỏ.

17
00:00:42,870 --> 00:00:45,624
Nhưng nếu mảng được sắp xếp,
chúng ta có thể làm điều đó, bởi vì chúng tôi

18
00:00:45,624 --> 00:00:48,040
biết rằng tất cả mọi thứ để các
trái của nơi chúng tôi đang có

19
00:00:48,040 --> 00:00:50,500
được thấp hơn
giá trị chúng tôi hiện tại.

20
00:00:50,500 --> 00:00:52,300
Và tất cả mọi thứ để các
quyền của chúng ta ở đâu

21
00:00:52,300 --> 00:00:55,040
phải lớn hơn giá trị
Hiện tại chúng tôi đang tìm kiếm.

22
00:00:55,040 --> 00:00:58,710
>> Vì vậy, các mã giả là những gì
các bước để tìm kiếm nhị phân?

23
00:00:58,710 --> 00:01:02,310
Chúng tôi lặp lại quá trình này cho đến khi
mảng hoặc, như chúng ta tiến hành thông qua,

24
00:01:02,310 --> 00:01:07,740
mảng phụ, miếng nhỏ hơn
các mảng ban đầu, có kích thước 0.

25
00:01:07,740 --> 00:01:10,960
Tính trung điểm
của mảng phụ hiện hành.

26
00:01:10,960 --> 00:01:14,460
>> Nếu các giá trị mà bạn đang tìm kiếm là
trong đó phần tử của mảng, dừng lại.

27
00:01:14,460 --> 00:01:15,030
Bạn tìm thấy nó.

28
00:01:15,030 --> 00:01:16,550
Thật tuyệt.

29
00:01:16,550 --> 00:01:19,610
Nếu không, nếu mục tiêu là
ít hơn so với những gì ở giữa,

30
00:01:19,610 --> 00:01:23,430
do đó, nếu giá trị, chúng tôi đang tìm kiếm
cho là thấp hơn so với những gì chúng ta thấy,

31
00:01:23,430 --> 00:01:26,780
lặp lại quá trình này một lần nữa, nhưng
thay đổi điểm kết thúc, thay vì

32
00:01:26,780 --> 00:01:29,300
của là gốc
hoàn thành mảng đầy đủ,

33
00:01:29,300 --> 00:01:34,110
được chỉ sang bên trái
của nơi mà chúng ta chỉ nhìn.

34
00:01:34,110 --> 00:01:38,940
>> Chúng tôi biết rằng giữa là quá cao,
hoặc các mục tiêu đã được ít hơn giữa,

35
00:01:38,940 --> 00:01:42,210
và do đó, nó phải tồn tại, nếu nó
tồn tại ở tất cả các mảng,

36
00:01:42,210 --> 00:01:44,660
một nơi nào đó bên trái của trung điểm.

37
00:01:44,660 --> 00:01:48,120
Và vì vậy chúng tôi sẽ thiết lập các mảng
địa chỉ sang bên trái

38
00:01:48,120 --> 00:01:51,145
trung điểm như điểm kết thúc mới.

39
00:01:51,145 --> 00:01:53,770
Ngược lại, nếu mục tiêu là
lớn hơn những gì ở giữa,

40
00:01:53,770 --> 00:01:55,750
chúng tôi làm chính xác cùng
quá trình, nhưng thay vào đó chúng tôi

41
00:01:55,750 --> 00:01:59,520
thay đổi điểm khởi đầu là
ngay bên phải của trung điểm

42
00:01:59,520 --> 00:02:00,680
chúng ta chỉ cần tính toán.

43
00:02:00,680 --> 00:02:03,220
Và sau đó, chúng tôi bắt đầu quá trình một lần nữa.

44
00:02:03,220 --> 00:02:05,220
>> Hãy hình dung này, OK?

45
00:02:05,220 --> 00:02:08,620
Vì vậy, có rất nhiều đi và về đây,
nhưng đây là một mảng của 15 yếu tố.

46
00:02:08,620 --> 00:02:11,400
Và chúng ta sẽ được theo dõi
của rất nhiều các công cụ thời gian này.

47
00:02:11,400 --> 00:02:13,870
Vì vậy, trong tìm kiếm tuyến tính, chúng tôi đã
chỉ quan tâm đến một mục tiêu.

48
00:02:13,870 --> 00:02:15,869
Nhưng lần này, chúng tôi muốn
quan tâm đến nơi là chúng tôi

49
00:02:15,869 --> 00:02:18,480
bắt đầu tìm kiếm ở đâu,
Chúng ta dừng lại nhìn,

50
00:02:18,480 --> 00:02:21,876
và trung điểm là những gì
của mảng hiện hành.

51
00:02:21,876 --> 00:02:23,250
Vì vậy, ở đây chúng tôi đi với tìm kiếm nhị phân.

52
00:02:23,250 --> 00:02:25,290
Chúng tôi khá nhiều tốt để đi, phải không?

53
00:02:25,290 --> 00:02:28,650
Tôi chỉ cần đi để đặt xuống
dưới đây là một tập hợp các chỉ số.

54
00:02:28,650 --> 00:02:32,430
Đây là yếu tố cơ bản chỉ là những gì
của mảng, chúng tôi đang nói về.

55
00:02:32,430 --> 00:02:34,500
Với tìm kiếm tuyến tính, chúng tôi
quan tâm, bởi vì như chúng ta

56
00:02:34,500 --> 00:02:36,800
cần phải biết có bao nhiêu
yếu tố chúng ta lặp qua,

57
00:02:36,800 --> 00:02:40,010
nhưng chúng tôi không thực sự quan tâm những gì
yếu tố hiện tại chúng tôi đang tìm kiếm.

58
00:02:40,010 --> 00:02:41,014
Trong cuộc tìm kiếm nhị phân, chúng ta làm.

59
00:02:41,014 --> 00:02:42,930
Và do đó, những chỉ
đó như là một hướng dẫn rất ít.

60
00:02:42,930 --> 00:02:44,910
>> Vì vậy, chúng ta có thể bắt đầu, phải không?

61
00:02:44,910 --> 00:02:46,240
Vâng, không khá.

62
00:02:46,240 --> 00:02:48,160
Hãy nhớ những gì tôi nói
về tìm kiếm nhị phân?

63
00:02:48,160 --> 00:02:50,955
Chúng ta không thể làm điều đó trên một
mảng được phân loại hoặc khác,

64
00:02:50,955 --> 00:02:55,820
chúng tôi không đảm bảo rằng
Các nguyên tố hoặc giá trị nhất định là không

65
00:02:55,820 --> 00:02:57,650
là vô tình
bỏ đi khi chúng ta chỉ

66
00:02:57,650 --> 00:02:59,920
quyết định bỏ qua một nửa của mảng.

67
00:02:59,920 --> 00:03:02,574
>> Vì vậy, bước một với tìm kiếm nhị phân
là bạn phải có một mảng được sắp xếp.

68
00:03:02,574 --> 00:03:05,240
Và bạn có thể sử dụng bất kỳ phân loại
các thuật toán, chúng tôi đã nói chuyện về

69
00:03:05,240 --> 00:03:06,700
để giúp bạn có được vị trí đó.

70
00:03:06,700 --> 00:03:10,370
Vì vậy, bây giờ, chúng ta đang ở trong một vị trí mà
chúng ta có thể thực hiện tìm kiếm nhị phân.

71
00:03:10,370 --> 00:03:12,560
>> Vì vậy, hãy lặp lại quá trình
từng bước và giữ

72
00:03:12,560 --> 00:03:14,830
theo dõi những gì đang xảy ra khi chúng ta đi.

73
00:03:14,830 --> 00:03:17,980
Vì vậy, đầu tiên chúng ta cần làm là tính toán
trung điểm của các mảng hiện hành.

74
00:03:17,980 --> 00:03:20,620
Vâng, chúng tôi sẽ nói rằng chúng ta, trước
tất cả, tìm kiếm giá trị 19.

75
00:03:20,620 --> 00:03:22,290
Chúng tôi đang cố gắng để tìm ra số 19.

76
00:03:22,290 --> 00:03:25,380
Yếu tố đầu tiên của việc này
mảng nằm ở chỉ số zero,

77
00:03:25,380 --> 00:03:28,880
và yếu tố cuối cùng này
mảng được đặt tại số 14.

78
00:03:28,880 --> 00:03:31,430
Và vì vậy chúng tôi sẽ gọi cho những người bắt đầu và kết thúc.

79
00:03:31,430 --> 00:03:35,387
>> Vì vậy, chúng tôi tính toán trung điểm của
thêm 0 cộng với 14 chia cho 2;

80
00:03:35,387 --> 00:03:36,720
trung điểm khá đơn giản.

81
00:03:36,720 --> 00:03:40,190
Và chúng ta có thể nói rằng
trung điểm hiện nay là 7.

82
00:03:40,190 --> 00:03:43,370
Vậy là 15 gì chúng tôi đang tìm kiếm?

83
00:03:43,370 --> 00:03:43,940
Không, nó không phải.

84
00:03:43,940 --> 00:03:45,270
Chúng tôi đang tìm kiếm 19.

85
00:03:45,270 --> 00:03:49,400
Nhưng chúng ta biết rằng 19 là lớn hơn
so với những gì chúng tôi tìm thấy ở giữa.

86
00:03:49,400 --> 00:03:52,470
>> Vì vậy, những gì chúng ta có thể làm là
thay đổi điểm khởi đầu

87
00:03:52,470 --> 00:03:57,280
để được ở ngay bên phải của
trung điểm, và lặp lại quá trình này một lần nữa.

88
00:03:57,280 --> 00:04:01,690
Và khi chúng ta làm điều đó, bây giờ chúng ta nói
điểm khởi đầu mới là mảng vị trí 8.

89
00:04:01,690 --> 00:04:07,220
Những gì chúng ta đã thực hiện có hiệu quả là
tất cả mọi thứ bỏ qua bên trái của 15.

90
00:04:07,220 --> 00:04:09,570
Chúng tôi đã loại bỏ một nửa
của vấn đề, và bây giờ,

91
00:04:09,570 --> 00:04:13,510
thay vì phải tìm kiếm
hơn 15 phần tử trong mảng của chúng tôi,

92
00:04:13,510 --> 00:04:15,610
chúng ta chỉ cần tìm kiếm trên 7.

93
00:04:15,610 --> 00:04:17,706
Vì vậy, 8 là điểm khởi đầu mới.

94
00:04:17,706 --> 00:04:19,600
14 vẫn là điểm kết thúc.

95
00:04:19,600 --> 00:04:21,430
>> Và bây giờ, chúng tôi đi qua này một lần nữa.

96
00:04:21,430 --> 00:04:22,810
Chúng tôi tính toán trung điểm mới.

97
00:04:22,810 --> 00:04:27,130
8 cộng với 14 là 22, chia cho 2 là 11.

98
00:04:27,130 --> 00:04:28,660
Đây có phải là những gì chúng tôi đang tìm kiếm?

99
00:04:28,660 --> 00:04:30,110
Không, nó không phải.

100
00:04:30,110 --> 00:04:32,930
Chúng tôi đang tìm kiếm một giá trị đó là
ít hơn so với những gì chúng ta vừa được tìm thấy.

101
00:04:32,930 --> 00:04:34,721
Vì vậy, chúng ta sẽ lặp lại
quá trình một lần nữa.

102
00:04:34,721 --> 00:04:38,280
Chúng tôi sẽ thay đổi điểm kết thúc
là ngay bên trái của trung điểm.

103
00:04:38,280 --> 00:04:41,800
Vì vậy, điểm kết thúc mới trở thành 10.

104
00:04:41,800 --> 00:04:44,780
Và bây giờ, đó là phần duy nhất của
mảng chúng ta phải sắp xếp thông qua.

105
00:04:44,780 --> 00:04:48,460
Vì vậy, bây giờ chúng tôi đã loại bỏ
12 trong số 15 yếu tố.

106
00:04:48,460 --> 00:04:51,550
Chúng tôi biết rằng nếu 19
tồn tại trong mảng, nó

107
00:04:51,550 --> 00:04:57,210
phải tồn tại một nơi nào đó giữa phần tử
số 8 và yếu tố số 10.

108
00:04:57,210 --> 00:04:59,400
>> Vì vậy, chúng tôi tính toán trung điểm mới một lần nữa.

109
00:04:59,400 --> 00:05:02,900
8 cộng với 10 là 18, chia cho 2 là 9.

110
00:05:02,900 --> 00:05:05,074
Và trong trường hợp này, nhìn,
mục tiêu là ở giữa.

111
00:05:05,074 --> 00:05:06,740
Chúng tôi tìm thấy chính xác những gì chúng tôi đang tìm kiếm.

112
00:05:06,740 --> 00:05:07,780
Chúng ta có thể dừng lại.

113
00:05:07,780 --> 00:05:10,561
Chúng tôi đã hoàn thành công
tìm kiếm nhị phân.

114
00:05:10,561 --> 00:05:11,060
Được rồi.

115
00:05:11,060 --> 00:05:13,930
Vì vậy, chúng ta biết thuật toán này
hoạt động nếu mục tiêu là

116
00:05:13,930 --> 00:05:16,070
một nơi nào đó bên trong của mảng.

117
00:05:16,070 --> 00:05:19,060
Có hoạt thuật toán này nếu
các mục tiêu không phải là trong mảng?

118
00:05:19,060 --> 00:05:20,810
Vâng, chúng ta hãy bắt đầu nó
một lần nữa, và lần này,

119
00:05:20,810 --> 00:05:23,380
chúng ta hãy tìm kiếm các phần tử
16, mà trực quan chúng ta có thể nhìn thấy

120
00:05:23,380 --> 00:05:25,620
không tồn tại bất cứ nơi nào trong mảng.

121
00:05:25,620 --> 00:05:27,110
>> Điểm khởi đầu là một lần nữa 0.

122
00:05:27,110 --> 00:05:28,590
Điểm cuối cùng là một lần nữa 14.

123
00:05:28,590 --> 00:05:32,490
Đó là những chỉ số của các đầu tiên và
phần tử cuối cùng của mảng hoàn chỉnh.

124
00:05:32,490 --> 00:05:36,057
Và chúng ta sẽ đi qua các quá trình chúng ta chỉ
đi qua một lần nữa, cố gắng để tìm thấy 16,

125
00:05:36,057 --> 00:05:39,140
mặc dù trực quan, chúng ta có thể đã
nói rằng nó sẽ không có mặt ở đó.

126
00:05:39,140 --> 00:05:43,450
Chúng tôi chỉ muốn chắc chắn rằng thuật toán này
sẽ, trên thực tế, vẫn còn làm việc trong một số cách

127
00:05:43,450 --> 00:05:46,310
và không chỉ để lại cho chúng tôi
bị mắc kẹt trong một vòng lặp vô hạn.

128
00:05:46,310 --> 00:05:48,190
>> Vì vậy, bước đầu tiên là gì?

129
00:05:48,190 --> 00:05:50,230
Tính trung điểm
của mảng hiện hành.

130
00:05:50,230 --> 00:05:52,790
Trung điểm là gì
của mảng hiện tại?

131
00:05:52,790 --> 00:05:54,410
Vâng, đó là 7, phải không?

132
00:05:54,410 --> 00:05:57,560
14 cộng với 0 chia cho 2 là 7.

133
00:05:57,560 --> 00:05:59,280
15 điều chúng ta đang tìm kiếm?

134
00:05:59,280 --> 00:05:59,780
Không.

135
00:05:59,780 --> 00:06:02,930
Nó khá gần, nhưng chúng tôi đang tìm kiếm
cho một giá trị hơi lớn hơn thế.

136
00:06:02,930 --> 00:06:06,310
>> Vì vậy, chúng ta biết rằng nó sẽ
có nơi nào để trái 15.

137
00:06:06,310 --> 00:06:08,540
Các mục tiêu lớn hơn
những gì trong trung điểm.

138
00:06:08,540 --> 00:06:12,450
Và vì vậy chúng tôi thiết lập điểm khởi đầu mới đến
là ngay bên phải của giữa.

139
00:06:12,450 --> 00:06:16,130
Trung điểm hiện nay là 7, do đó
hãy nói rằng điểm khởi đầu mới là 8.

140
00:06:16,130 --> 00:06:18,130
Và những gì chúng ta đã có hiệu quả
thực hiện một lần nữa bị bỏ qua

141
00:06:18,130 --> 00:06:21,150
toàn bộ nửa bên trái của mảng.

142
00:06:21,150 --> 00:06:23,750
>> Bây giờ, chúng ta lập lại
xử lý thêm một lần nữa.

143
00:06:23,750 --> 00:06:24,910
Tính trung điểm mới.

144
00:06:24,910 --> 00:06:29,350
8 cộng với 14 là 22, chia cho 2 là 11.

145
00:06:29,350 --> 00:06:31,060
23 điều chúng ta đang tìm kiếm?

146
00:06:31,060 --> 00:06:31,870
Tiếc là không có.

147
00:06:31,870 --> 00:06:34,930
Chúng tôi đang tìm kiếm một giá trị
đó là ít hơn 23.

148
00:06:34,930 --> 00:06:37,850
Và như vậy trong trường hợp này, chúng ta sẽ
để thay đổi điểm kết thúc là chỉ

149
00:06:37,850 --> 00:06:40,035
bên trái của trung điểm hiện tại.

150
00:06:40,035 --> 00:06:43,440
Trung điểm hiện tại là 11, và
vì vậy chúng tôi sẽ thiết lập các điểm kết thúc mới

151
00:06:43,440 --> 00:06:46,980
cho thời gian tới chúng tôi đi
thông qua quá trình này đến 10.

152
00:06:46,980 --> 00:06:48,660
>> Một lần nữa, chúng tôi đi qua quá trình này một lần nữa.

153
00:06:48,660 --> 00:06:49,640
Tính trung điểm.

154
00:06:49,640 --> 00:06:53,100
8 cộng với 10 chia cho 2 là 9.

155
00:06:53,100 --> 00:06:54,750
19 điều chúng ta đang tìm kiếm?

156
00:06:54,750 --> 00:06:55,500
Tiếc là không có.

157
00:06:55,500 --> 00:06:58,050
Chúng tôi vẫn đang tìm kiếm
một số ít hơn.

158
00:06:58,050 --> 00:07:02,060
Vì vậy, chúng tôi sẽ thay đổi điểm kết thúc thời gian này
là ngay bên trái của trung điểm.

159
00:07:02,060 --> 00:07:05,532
Trung điểm hiện tại là 9,
do đó, điểm cuối cùng sẽ là 8.

160
00:07:05,532 --> 00:07:07,920
Và bây giờ, chúng tôi chỉ tìm
tại một mảng yếu tố duy nhất.

161
00:07:07,920 --> 00:07:10,250
>> Trung điểm của mảng này là gì?

162
00:07:10,250 --> 00:07:13,459
Vâng, nó bắt đầu lúc 8, nó
kết thúc vào 8, trung điểm là 8.

163
00:07:13,459 --> 00:07:14,750
Đó là những gì chúng tôi đang tìm kiếm?

164
00:07:14,750 --> 00:07:16,339
Có phải chúng ta đang tìm kiếm 17?

165
00:07:16,339 --> 00:07:17,380
Không, chúng tôi đang tìm kiếm 16.

166
00:07:17,380 --> 00:07:20,160
Vì vậy, nếu nó tồn tại trong mảng,
nó phải tồn tại một nơi nào đó

167
00:07:20,160 --> 00:07:21,935
bên trái của nơi chúng tôi đang có.

168
00:07:21,935 --> 00:07:23,060
Vì vậy, những gì chúng ta sẽ làm gì?

169
00:07:23,060 --> 00:07:26,610
Vâng, chúng tôi sẽ thiết lập các điểm kết thúc là chỉ
bên trái của trung điểm hiện tại.

170
00:07:26,610 --> 00:07:29,055
Vì vậy, chúng tôi sẽ thay đổi điểm kết thúc 7.

171
00:07:29,055 --> 00:07:32,120
Bạn có thấy gì chỉ
xảy ra ở đây, mặc dù?

172
00:07:32,120 --> 00:07:33,370
Nhìn lên ở đây bây giờ.

173
00:07:33,370 --> 00:07:35,970
>> Bắt đầu bây giờ là lớn hơn hết.

174
00:07:35,970 --> 00:07:39,620
Hiệu quả, hai đầu
các mảng của chúng tôi đã vượt qua,

175
00:07:39,620 --> 00:07:42,252
và điểm khởi đầu là
bây giờ sau khi các điểm kết thúc.

176
00:07:42,252 --> 00:07:43,960
Vâng, điều đó không có
thực hiện bất kỳ ý nghĩa, phải không?

177
00:07:43,960 --> 00:07:47,960
Vì vậy, bây giờ, chúng ta những gì chúng ta có thể nói là
có một mảng phụ kích thước 0.

178
00:07:47,960 --> 00:07:50,110
Và một khi chúng ta nhận được đến
thời điểm này, chúng tôi có thể bây giờ

179
00:07:50,110 --> 00:07:53,940
đảm bảo yếu tố đó 16
không tồn tại trong mảng,

180
00:07:53,940 --> 00:07:56,280
vì điểm khởi đầu
và điểm kết thúc đã vượt qua.

181
00:07:56,280 --> 00:07:58,340
Và do đó, nó không có ở đó.

182
00:07:58,340 --> 00:08:01,340
Bây giờ, nhận thấy rằng điều này là hơi
khác với điểm bắt đầu và kết thúc

183
00:08:01,340 --> 00:08:02,900
chỉ là cùng.

184
00:08:02,900 --> 00:08:05,030
Nếu chúng ta tìm kiếm
17, nó sẽ có

185
00:08:05,030 --> 00:08:08,870
được trong mảng, và điểm khởi đầu
và điểm kết thúc mà lặp cuối cùng

186
00:08:08,870 --> 00:08:11,820
trước khi những điểm vượt qua,
chúng ta sẽ tìm ra 17 đó.

187
00:08:11,820 --> 00:08:15,510
Đó là chỉ khi họ qua đó chúng ta có thể
đảm bảo rằng các phần tử không

188
00:08:15,510 --> 00:08:17,180
tồn tại trong mảng.

189
00:08:17,180 --> 00:08:20,260
>> Vì vậy, chúng ta hãy ít hơn rất nhiều
bước so với tìm kiếm tuyến tính.

190
00:08:20,260 --> 00:08:23,250
Trong trường hợp xấu nhất, chúng tôi đã có
để chia tay một danh sách các yếu tố n

191
00:08:23,250 --> 00:08:27,770
lặp đi lặp lại một nửa để tìm mục tiêu,
hoặc vì các yếu tố mục tiêu

192
00:08:27,770 --> 00:08:33,110
sẽ là một nơi nào đó ở cuối cùng
chia, hoặc nó không tồn tại.

193
00:08:33,110 --> 00:08:37,830
Vì vậy, trong trường hợp xấu nhất, chúng ta phải
chia ra các array-- bạn có biết?

194
00:08:37,830 --> 00:08:40,510
Nhật ký của n lần; chúng tôi
phải cắt giảm các vấn đề

195
00:08:40,510 --> 00:08:42,610
trong một nửa số lần nhất định.

196
00:08:42,610 --> 00:08:45,160
Đó là số lần là log n.

197
00:08:45,160 --> 00:08:46,510
>> Trường hợp kịch bản tốt nhất là gì?

198
00:08:46,510 --> 00:08:48,899
Vâng, lần đầu tiên chúng ta
tính trung điểm,

199
00:08:48,899 --> 00:08:50,190
chúng ta tìm thấy những gì chúng tôi đang tìm kiếm.

200
00:08:50,190 --> 00:08:52,150
Trong tất cả các trang trước
ví dụ về tìm kiếm nhị phân

201
00:08:52,150 --> 00:08:55,489
chúng tôi vừa đi qua, nếu chúng ta có
được tìm kiếm các nguyên tố 15,

202
00:08:55,489 --> 00:08:57,030
chúng ta sẽ thấy rằng ngay lập tức.

203
00:08:57,030 --> 00:08:58,321
Đó cũng là lúc bắt đầu.

204
00:08:58,321 --> 00:09:01,200
Đó là trung điểm của
những nỗ lực đầu tiên tại một sự chia rẽ

205
00:09:01,200 --> 00:09:03,950
của một bộ phận trong tìm kiếm nhị phân.

206
00:09:03,950 --> 00:09:06,350
>> Và như vậy trong tồi tệ nhất
trường hợp, tìm kiếm nhị phân chạy

207
00:09:06,350 --> 00:09:11,580
trong log n, mà là tốt hơn đáng kể
so với tìm kiếm tuyến tính, trong trường hợp xấu nhất.

208
00:09:11,580 --> 00:09:16,210
Trong trường hợp tốt nhất, nhị phân
tìm kiếm chạy trong omega của 1.

209
00:09:16,210 --> 00:09:18,990
Vì vậy, tìm kiếm nhị phân là rất nhiều
tốt hơn so với tìm kiếm tuyến tính,

210
00:09:18,990 --> 00:09:23,270
nhưng bạn phải đối phó với quá trình
phân loại các mảng của bạn đầu tiên trước khi bạn có thể

211
00:09:23,270 --> 00:09:26,140
tận dụng sức mạnh của tìm kiếm nhị phân.

212
00:09:26,140 --> 00:09:27,130
>> Tôi Doug Lloyd.

213
00:09:27,130 --> 00:09:29,470
Đây là CS 50.

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