1
00:00:00,000 --> 00:00:09,560

2
00:00:09,560 --> 00:00:13,120
>> ZAMYLA CHAN: Điều đầu tiên bạn có thể
thông báo về tìm là chúng ta đã

3
00:00:13,120 --> 00:00:14,520
có mã viết cho chúng ta.

4
00:00:14,520 --> 00:00:16,219
Này được gọi là đang phân phối.

5
00:00:16,219 --> 00:00:19,060
Vì vậy, chúng tôi không chỉ viết riêng của chúng tôi
mã từ đầu nữa.

6
00:00:19,060 --> 00:00:23,870
Thay vào đó, chúng ta điền vào các khoảng trống
ở một số mã đã có từ trước.

7
00:00:23,870 --> 00:00:28,860
>> Chương trình sẽ nhắc cho find.c số
để điền vào các đống cỏ khô, tìm kiếm các

8
00:00:28,860 --> 00:00:33,260
đống cỏ khô cho một người dùng gửi kim,
và nó thực hiện điều này bằng cách gọi loại và

9
00:00:33,260 --> 00:00:36,660
tìm kiếm, chức năng xác định
trong helpers.c.

10
00:00:36,660 --> 00:00:38,740
Vì vậy, find.c được viết rồi.

11
00:00:38,740 --> 00:00:41,840
Công việc của bạn là viết những người giúp đỡ.

12
00:00:41,840 --> 00:00:42,940
>> Vì vậy, những gì chúng ta làm gì?

13
00:00:42,940 --> 00:00:45,270
Chúng tôi đang thực hiện hai chức năng.

14
00:00:45,270 --> 00:00:50,110
Tìm kiếm, trả về đúng nếu một giá trị
được tìm thấy trong đống cỏ khô, trở về

15
00:00:50,110 --> 00:00:52,430
sai nếu giá trị là
không trong đống cỏ khô.

16
00:00:52,430 --> 00:00:59,060
Và sau đó chúng tôi cũng đang thực hiện sắp xếp,
mà sắp xếp các mảng được gọi là giá trị.

17
00:00:59,060 --> 00:01:01,120
Vì vậy, hãy giải quyết tìm kiếm.

18
00:01:01,120 --> 00:01:04,550
>> Tìm kiếm hiện đang thực hiện
như một tìm kiếm tuyến tính.

19
00:01:04,550 --> 00:01:06,620
Nhưng bạn có thể làm tốt hơn nhiều hơn thế.

20
00:01:06,620 --> 00:01:11,610
Tìm kiếm tuyến tính được thực hiện trong O n
thời gian, mà là khá chậm, mặc dù nó

21
00:01:11,610 --> 00:01:14,920
có thể tìm kiếm bất kỳ danh sách cho nó.

22
00:01:14,920 --> 00:01:21,190
Công việc của bạn là để thực hiện tìm kiếm nhị phân,
đã chạy thời gian O của log n.

23
00:01:21,190 --> 00:01:22,200
Đó là khá nhanh.

24
00:01:22,200 --> 00:01:24,240
>> Nhưng có một quy định.

25
00:01:24,240 --> 00:01:28,910
Tìm kiếm nhị phân chỉ có thể tìm kiếm
thông qua danh sách được sắp xếp trước.

26
00:01:28,910 --> 00:01:31,450
Tại sao vậy?

27
00:01:31,450 --> 00:01:33,690
Vâng, chúng ta hãy xem một ví dụ.

28
00:01:33,690 --> 00:01:37,350
Đưa ra một mảng các giá trị, các đống cỏ khô,
chúng ta sẽ được tìm kiếm

29
00:01:37,350 --> 00:01:41,510
cho một cây kim, và trong này
Ví dụ, số nguyên 3.

30
00:01:41,510 --> 00:01:45,220
>> Cách mà tìm kiếm nhị phân hoạt động là
chúng ta so sánh giá trị giữa

31
00:01:45,220 --> 00:01:49,430
các mảng kim, nhiều như thế nào
chúng tôi đã mở một cuốn sách điện thoại vào giữa

32
00:01:49,430 --> 00:01:51,720
trang trong Tuần 0.

33
00:01:51,720 --> 00:01:55,710
Vì vậy, sau khi so sánh giá trị giữa để
kim, bạn có thể loại bỏ một trong hai

34
00:01:55,710 --> 00:01:59,620
trái hoặc nửa bên phải của mảng
bằng cách thắt chặt giới hạn của bạn.

35
00:01:59,620 --> 00:02:04,450
Trong trường hợp này, vì 3, kim của chúng tôi, là
ít hơn 10, giá trị giữa,

36
00:02:04,450 --> 00:02:07,060
đúng ràng buộc có thể giảm.

37
00:02:07,060 --> 00:02:09,470
>> Nhưng cố gắng làm cho giới hạn của bạn
như chặt chẽ nhất có thể.

38
00:02:09,470 --> 00:02:12,690
Nếu giá trị trung không phải là kim,
sau đó bạn biết rằng bạn không cần phải

39
00:02:12,690 --> 00:02:14,070
bao gồm nó trong tìm kiếm của bạn.

40
00:02:14,070 --> 00:02:18,390
Vì vậy, bên phải của bạn bị ràng buộc có thể thắt chặt
giới hạn tìm kiếm nhiều hơn một chút xíu,

41
00:02:18,390 --> 00:02:22,840
vv và vv, cho đến khi
bạn tìm thấy kim của bạn.

42
00:02:22,840 --> 00:02:24,580
>> Vì vậy, những gì hiện các giả
đang như thế nào?

43
00:02:24,580 --> 00:02:28,980
Vâng, trong khi chúng tôi vẫn đang tìm kiếm thông qua
danh sách và vẫn còn có

44
00:02:28,980 --> 00:02:33,540
các yếu tố để xem xét trong, chúng ta giữa
danh sách và so sánh

45
00:02:33,540 --> 00:02:36,020
giá trị trung bình đến kim của chúng tôi.

46
00:02:36,020 --> 00:02:38,380
Nếu chúng bằng nhau, thì có nghĩa là chúng tôi đã
tìm thấy kim, và chúng ta có thể

47
00:02:38,380 --> 00:02:40,160
return true.

48
00:02:40,160 --> 00:02:43,940
>> Nếu không, nếu kim nhỏ hơn
giá trị trung bình, sau đó có nghĩa là chúng tôi

49
00:02:43,940 --> 00:02:48,350
có thể loại bỏ nửa bên phải và chỉ
tìm kiếm bên trái của mảng.

50
00:02:48,350 --> 00:02:51,860
Nếu không, chúng tôi sẽ tìm kiếm
phía bên phải của mảng.

51
00:02:51,860 --> 00:02:55,470
Và cuối cùng, nếu bạn không có bất kỳ
nhiều yếu tố còn lại để tìm kiếm nhưng bạn

52
00:02:55,470 --> 00:02:58,030
đã không tìm thấy kim của bạn chưa,
sau đó bạn trở lại sai.

53
00:02:58,030 --> 00:03:02,960
Vì kim chắc chắn
không có trong đống cỏ khô.

54
00:03:02,960 --> 00:03:06,200
>> Bây giờ, có một điều gọn về giả này
mã trong tìm kiếm nhị phân là nó có thể

55
00:03:06,200 --> 00:03:11,000
được hiểu là một hoặc lặp đi lặp lại
hoặc thực hiện đệ quy.

56
00:03:11,000 --> 00:03:14,900
Vì vậy, nó sẽ là đệ quy nếu bạn gọi
chức năng tìm kiếm trong tìm kiếm

57
00:03:14,900 --> 00:03:18,400
hoạt động ở hai nửa của mảng.

58
00:03:18,400 --> 00:03:20,750
Chúng tôi sẽ giới thiệu đệ quy một chút
sau này trong khóa học.

59
00:03:20,750 --> 00:03:23,210
Nhưng tôi biết rằng nó là một lựa chọn
nếu bạn muốn thử.

60
00:03:23,210 --> 00:03:24,460