1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Tìm kiếm tuyến tính]

2
00:00:02,430 --> 00:00:04,430
[Patrick Schmid, Đại học Harvard]

3
00:00:04,430 --> 00:00:07,430
[This Is CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Tìm kiếm là một cái gì đó mà bạn có thể làm nhiều hơn bạn nghĩ.

5
00:00:09,440 --> 00:00:11,600
Rõ ràng, mỗi khi bạn mở một trình duyệt web

6
00:00:11,600 --> 00:00:12,890
và tìm kiếm cho một trang web

7
00:00:12,890 --> 00:00:15,620
hoặc tìm kiếm cho bạn bè của bạn trên trang web yêu thích mạng xã hội của bạn -

8
00:00:15,620 --> 00:00:16,610
bạn đang tìm kiếm.

9
00:00:16,610 --> 00:00:19,690
Nhưng đó chỉ là một phần nhỏ trong việc tìm kiếm mà bạn làm trên một cơ sở hàng ngày.

10
00:00:19,690 --> 00:00:21,720
Khi bạn muốn tìm là một trong những chiếc áo xanh trong tủ quần áo,

11
00:00:21,720 --> 00:00:23,620
hoặc áo màu đỏ hoàn hảo cho dịp này,

12
00:00:23,620 --> 00:00:24,730
bạn đang tìm kiếm.

13
00:00:24,730 --> 00:00:26,640
Khi bạn đi đến một cửa hàng mà bạn chưa bao giờ đến trước khi,

14
00:00:26,640 --> 00:00:28,590
và bạn đang tìm kiếm bông cải xanh trong lối đi sản phẩm

15
00:00:28,590 --> 00:00:29,650
bạn đang tìm kiếm.

16
00:00:29,650 --> 00:00:31,050
Những gì bạn có thể đã bắt đầu để ý

17
00:00:31,050 --> 00:00:32,820
là tùy thuộc vào những gì bạn đang tìm kiếm

18
00:00:32,820 --> 00:00:35,340
hoặc các mục được tổ chức như thế nào khi bạn đang tìm kiếm chúng

19
00:00:35,340 --> 00:00:37,670
nó có một hiệu lực về việc làm thế nào bạn tìm kiếm.

20
00:00:37,670 --> 00:00:40,990
Ví dụ, nếu áo sơ mi của bạn được treo trong tủ quần áo,

21
00:00:40,990 --> 00:00:42,840
bạn có thể có lẽ chỉ cần chọn nó ra mà không có nhiều tìm kiếm.

22
00:00:42,840 --> 00:00:45,300
Nếu bạn đang giả định bạn phải đi bộ xuống các lối đi

23
00:00:45,300 --> 00:00:48,750
để có được bông cải xanh, bạn có thể phải xem xét tất cả các loại rau khác

24
00:00:48,750 --> 00:00:49,940
trước khi bạn thấy rằng bông cải xanh.

25
00:00:49,940 --> 00:00:54,320
Tìm kiếm tuyến tính là một ví dụ về một trong những phương pháp như vậy - hoặc thuật toán tìm kiếm.

26
00:00:54,320 --> 00:00:55,550
Như tên của nó,

27
00:00:55,550 --> 00:00:59,240
phương pháp này tìm kiếm cho một mục trong một thời trang tuyến tính, một sau khi khác.

28
00:00:59,240 --> 00:01:02,080
Vì vậy, khi bạn đang tìm kiếm các kết quả từ công cụ tìm kiếm ưa thích của bạn

29
00:01:02,080 --> 00:01:03,850
và bạn đọc danh sách kết quả,

30
00:01:03,850 --> 00:01:05,290
bạn đang sử dụng tìm kiếm tuyến tính.

31
00:01:05,290 --> 00:01:06,830
Okay. Hãy xem một ví dụ.

32
00:01:06,830 --> 00:01:12,600
Nói rằng chúng tôi có một danh sách các số 2, 4, 0, 5, 3, 7, 8, và 1 -

33
00:01:12,600 --> 00:01:15,100
và chúng tôi đang tìm kiếm số 0.

34
00:01:15,100 --> 00:01:17,290
Rõ ràng, bạn chỉ có thể thấy rằng 0 là ở vị trí thứ ba.

35
00:01:17,290 --> 00:01:19,790
Tuy nhiên, một chương trình máy tính mà không phải là may mắn.

36
00:01:19,790 --> 00:01:22,030
Nó chỉ có thể "nhìn thấy" số một tại một thời điểm.

37
00:01:22,030 --> 00:01:23,840
Vì vậy, bắt đầu từ đầu danh sách,

38
00:01:23,840 --> 00:01:25,000
nó chỉ "nhìn thấy" 2.

39
00:01:25,000 --> 00:01:27,860
Chương trình sau đó kiểm tra là 2 bằng 0?

40
00:01:27,860 --> 00:01:30,320
Rõ ràng là không. Vì vậy, nó đi đến số tiếp theo, 4.

41
00:01:30,320 --> 00:01:33,320
4 0 bằng nhau không? Nope.

42
00:01:33,320 --> 00:01:35,460
Tiếp theo, 0. Ah! Zero là bằng 0.

43
00:01:35,460 --> 00:01:36,920
Hiện chúng tôi có nó! Đó là ở vị trí thứ ba.

44
00:01:36,920 --> 00:01:39,660
Okay. Hãy nhìn vào một số giả.

45
00:01:39,660 --> 00:01:43,320
Nó chỉ là một vài dòng dài, nhưng chúng ta hãy nhìn vào nó một dòng tại một thời điểm.

46
00:01:43,320 --> 00:01:46,740
Trước tiên, hãy xác định các chức năng - và chúng tôi sẽ gọi nó là tuyến tính tìm kiếm -

47
00:01:46,740 --> 00:01:49,040
và phải mất hai đối số - chìa khóa và mảng.

48
00:01:49,040 --> 00:01:50,770
Điều quan trọng là giá trị mà chúng ta đang tìm kiếm,

49
00:01:50,770 --> 00:01:53,160
do đó, trong ví dụ trước, đó là số không.

50
00:01:53,160 --> 00:01:55,080
Một mảng là một danh sách các số

51
00:01:55,080 --> 00:01:57,180
có tất cả các giá trị mà chúng ta sẽ tìm kiếm.

52
00:01:57,180 --> 00:02:00,010
Vì vậy, những gì chúng tôi muốn làm là chúng tôi muốn xem xét -

53
00:02:00,010 --> 00:02:02,030
từ tất cả các vị trí, do đó, bắt đầu từ khi bắt đầu của mảng

54
00:02:02,030 --> 00:02:05,260
đến tận phút cuối cùng của mảng nên chiều dài của mảng -

55
00:02:05,260 --> 00:02:07,580
nhìn vào tất cả các vị trí duy nhất và kiểm tra mỗi một.

56
00:02:07,580 --> 00:02:10,000
Vì vậy, đó là những gì mà "cho" vòng lặp được thực hiện.

57
00:02:10,000 --> 00:02:11,150
Và ở từng vị trí, chúng ta sẽ nói

58
00:02:11,150 --> 00:02:15,010
"Đó là giá trị tại vị trí đó hiện tại bằng phím mà chúng ta đang tìm kiếm?"

59
00:02:15,010 --> 00:02:17,000
Vì vậy, trong ví dụ trước một lần nữa, quan trọng là 0 -

60
00:02:17,000 --> 00:02:21,770
vì vậy chúng tôi đang nói đến "mảng tại vị trí tương đương về không?"

61
00:02:21,770 --> 00:02:24,640
Nếu có, chúng ta sẽ quay trở lại 'i' bởi vì đó là vị trí hiện tại chúng ta đang ở.

62
00:02:24,640 --> 00:02:25,710
Vì vậy, trong ví dụ trước,

63
00:02:25,710 --> 00:02:27,250
đó là vị trí thứ ba.

64
00:02:27,250 --> 00:02:29,330
Nếu chúng ta đã trải qua toàn bộ mảng

65
00:02:29,330 --> 00:02:30,690
và chúng tôi đã không tìm thấy bất cứ điều gì -

66
00:02:30,690 --> 00:02:32,180
vì vậy hãy nói rằng chúng tôi đang tìm kiếm con số 500

67
00:02:32,180 --> 00:02:33,860
rõ ràng là không phải trong ví dụ đó

68
00:02:33,860 --> 00:02:35,860
chúng tôi phải trả lại một cái gì đó,

69
00:02:35,860 --> 00:02:37,140
và chúng ta sẽ trở về -1.

70
00:02:37,140 --> 00:02:39,750
Và chúng tôi chỉ trả lại -1 bởi vì đó là một vị trí

71
00:02:39,750 --> 00:02:40,990
không tồn tại trong mảng.

72
00:02:40,990 --> 00:02:43,940
Và như vậy có nghĩa là khi bạn nhận được nó trở lại từ một hàm

73
00:02:43,940 --> 00:02:46,500
"Hmm, okay. Tôi đoán tôi đã không tìm thấy bất cứ điều gì.

74
00:02:46,500 --> 00:02:47,930
Vì vậy, mà 500 không bao giờ ở đó. "

75
00:02:47,930 --> 00:02:49,700
Những điều tốt đẹp về tìm kiếm tuyến tính là

76
00:02:49,700 --> 00:02:51,060
nó sẽ làm việc trên bất kỳ danh sách các mục,

77
00:02:51,060 --> 00:02:52,950
bất kể các mục được sắp xếp như thế nào.

78
00:02:52,950 --> 00:02:55,540
Nó không quan trọng nơi bông cải xanh là trong lối đi sản phẩm.

79
00:02:55,540 --> 00:02:57,070
Như khi bạn đi bộ xuống các lối đi từ đầu đến cuối,

80
00:02:57,070 --> 00:02:58,470
bạn đang bị ràng buộc để tìm thấy nó,

81
00:02:58,470 --> 00:03:00,800
giả sử các cửa hàng đã không chạy ra khỏi bông cải xanh, tất nhiên.

82
00:03:00,800 --> 00:03:04,200
Tuy nhiên, sức mạnh lớn nhất cũng là điểm yếu lớn nhất của nó.

83
00:03:04,200 --> 00:03:05,340
Giả sử bạn có một danh sách 200 số

84
00:03:05,340 --> 00:03:06,930
đều được sắp xếp từ 1 đến 200.

85
00:03:06,930 --> 00:03:09,420
Nếu bạn đang tìm kiếm cho số 198,

86
00:03:09,420 --> 00:03:11,060
bạn phải tìm kiếm gần như toàn bộ danh sách các con số

87
00:03:11,060 --> 00:03:12,960
trước khi bạn tìm thấy một trong những bạn đang tìm kiếm.

88
00:03:12,960 --> 00:03:14,460
Có phải là một cách tốt hơn!

89
00:03:14,460 --> 00:03:15,890
Hãy yên tâm là có.

90
00:03:15,890 --> 00:03:17,440
Nhưng, đó là một chủ đề cho video khác.

91
00:03:17,440 --> 00:03:19,280
Ngoài ra, không băn khoăn!

92
00:03:19,280 --> 00:03:22,650
Chỉ vì tìm kiếm tuyến tính không phải là giải pháp tốt nhất trong mọi tình huống,

93
00:03:22,650 --> 00:03:24,190
nó không có nghĩa rằng nó không có ích.

94
00:03:24,190 --> 00:03:27,130
Nếu không, làm thế nào bạn sẽ tìm thấy rằng bông cải xanh trong lối đi sản phẩm?

95
00:03:27,130 --> 00:03:29,910
Tên tôi là Patrick Schmid, và đây là CS50.

96
00:03:29,910 --> 00:03:32,000
[CS50.TV]