1
00:00:00,000 --> 00:00:02,430
[Powered by Google Translate] [Линеарна пребарување]

2
00:00:02,430 --> 00:00:04,430
[Патрик Шмид, Универзитетот Харвард]

3
00:00:04,430 --> 00:00:07,430
[Ова е CS50.] [CS50.TV]

4
00:00:07,430 --> 00:00:09,440
Пребарување е нешто што веројатно направи повеќе отколку што мислите.

5
00:00:09,440 --> 00:00:11,600
Очигледно, секој пат кога ќе се отвори веб пребарувач

6
00:00:11,600 --> 00:00:12,890
и пребарувањето за веб страната -

7
00:00:12,890 --> 00:00:15,620
или пребарај за вашите пријатели на вашиот омилен сајт за социјално вмрежување -

8
00:00:15,620 --> 00:00:16,610
ви се бараат.

9
00:00:16,610 --> 00:00:19,690
Но тоа е само мал дел од пребарување што го правите на дневна основа.

10
00:00:19,690 --> 00:00:21,720
Кога сакате да се најде дека една сина кошула во плакарот,

11
00:00:21,720 --> 00:00:23,620
или дека совршен црвена блуза за повод,

12
00:00:23,620 --> 00:00:24,730
сте во потрага.

13
00:00:24,730 --> 00:00:26,640
Кога одите во продавница, во којашто никогаш не сте биле пред,

14
00:00:26,640 --> 00:00:28,590
и сте во потрага за брокула во производство коридор

15
00:00:28,590 --> 00:00:29,650
сте во потрага.

16
00:00:29,650 --> 00:00:31,050
Она што може да започнете да се забележи

17
00:00:31,050 --> 00:00:32,820
е дека во зависност од она што го барате

18
00:00:32,820 --> 00:00:35,340
или како предмети се организираат кога сте во потрага по нив

19
00:00:35,340 --> 00:00:37,670
има ефект врз тоа како можете пребарување.

20
00:00:37,670 --> 00:00:40,990
На пример, ако вашиот кошули се виси во плакарот,

21
00:00:40,990 --> 00:00:42,840
можете да веројатно само да го одберам без многу бараат.

22
00:00:42,840 --> 00:00:45,300
Ако сте под претпоставка дека ќе мора да одат надолу по патека

23
00:00:45,300 --> 00:00:48,750
за да го добиете брокула, најверојатно треба да се погледне во сите други зеленчуци

24
00:00:48,750 --> 00:00:49,940
пред мислите дека брокулата.

25
00:00:49,940 --> 00:00:54,320
Линеарна пребарување е пример за една таква пребарување метод - или алгоритам.

26
00:00:54,320 --> 00:00:55,550
Како име имплицира,

27
00:00:55,550 --> 00:00:59,240
овој метод бара за ставка на еден линеарен начин, еден по друг.

28
00:00:59,240 --> 00:01:02,080
Значи, кога сте во потрага на резултатите од вашата омилена пребарувач

29
00:01:02,080 --> 00:01:03,850
и ќе прочитате долу на листата на резултати,

30
00:01:03,850 --> 00:01:05,290
го користите линеарно пребарување.

31
00:01:05,290 --> 00:01:06,830
Во ред. Ајде да погледнеме еден пример.

32
00:01:06,830 --> 00:01:12,600
Велат дека имаме листа на броеви - 2, 4, 0, 5, 3, 7, 8 и 1 -

33
00:01:12,600 --> 00:01:15,100
и ние сме во потрага за бројот 0.

34
00:01:15,100 --> 00:01:17,290
Очигледно, вие само може да се види дека 0 е во трета позиција.

35
00:01:17,290 --> 00:01:19,790
Но, компјутерска програма не е среќен.

36
00:01:19,790 --> 00:01:22,030
Тоа може само да "види" еден број во еден момент.

37
00:01:22,030 --> 00:01:23,840
Значи, уште на почетокот на листата,

38
00:01:23,840 --> 00:01:25,000
тоа само "гледа" 2.

39
00:01:25,000 --> 00:01:27,860
Потоа, програмата проверува - е 2 еднаква на 0?

40
00:01:27,860 --> 00:01:30,320
Очигледно не. Така тоа оди на следниот број, 4.

41
00:01:30,320 --> 00:01:33,320
Дали 4 еднакви 0? Не бе.

42
00:01:33,320 --> 00:01:35,460
Следниот, 0. Ах! Нула е еднакво на 0.

43
00:01:35,460 --> 00:01:36,920
Таму ние го имаме! Тоа е во трета позиција.

44
00:01:36,920 --> 00:01:39,660
Во ред. Да ги погледнеме некои pseudocode.

45
00:01:39,660 --> 00:01:43,320
Тоа е само неколку линии долго, но, ајде да се погледне во него една линија во време.

46
00:01:43,320 --> 00:01:46,740
Прво, нека дефинираат функција - и ние ќе го наречеме линеарно пребарување -

47
00:01:46,740 --> 00:01:49,040
и тоа трае два аргументи - клуч и низа.

48
00:01:49,040 --> 00:01:50,770
Клучот е тоа што вредноста што го барате,

49
00:01:50,770 --> 00:01:53,160
така и во претходниот пример, тоа беше нула.

50
00:01:53,160 --> 00:01:55,080
Низа е листа на броеви

51
00:01:55,080 --> 00:01:57,180
кој ги има сите вредности кои ние ќе треба да се бара.

52
00:01:57,180 --> 00:02:00,010
Значи, она што ние сакаме да направите е да сакаме да се погледне во -

53
00:02:00,010 --> 00:02:02,030
од сите позиции, па почнувајќи уште на самиот почеток на низата

54
00:02:02,030 --> 00:02:05,260
сусам самиот крај на низата - така што должината на низата -

55
00:02:05,260 --> 00:02:07,580
погледне во секоја позиција и да се провери секоја една.

56
00:02:07,580 --> 00:02:10,000
Значи тоа е она што "за" јамка прави.

57
00:02:10,000 --> 00:02:11,150
И во секоја позиција, ние ќе треба да се каже

58
00:02:11,150 --> 00:02:15,010
"Дали е тоа вредност во тоа моментална позиција еднаква на клуч, кој ние барате?"

59
00:02:15,010 --> 00:02:17,000
Значи - во претходниот пример, повторно, клучот е 0 -

60
00:02:17,000 --> 00:02:21,770
па ние сме велејќи: "Дали е низата на позиција i еднаков на нула?"

61
00:02:21,770 --> 00:02:24,640
Ако е така, ние ќе се вратат "i", бидејќи тоа е сегашната позиција сме во.

62
00:02:24,640 --> 00:02:25,710
Така, во претходниот пример,

63
00:02:25,710 --> 00:02:27,250
тоа беше третата позиција.

64
00:02:27,250 --> 00:02:29,330
Ако ние сме поминале низ целата низа

65
00:02:29,330 --> 00:02:30,690
и ние не пронашле ништо -

66
00:02:30,690 --> 00:02:32,180
па да речеме ние баравме бројот 500

67
00:02:32,180 --> 00:02:33,860
која очигледно не беше во таа пример -

68
00:02:33,860 --> 00:02:35,860
ние мора да се врати нешто,

69
00:02:35,860 --> 00:02:37,140
и ние ќе се врати -1.

70
00:02:37,140 --> 00:02:39,750
И ние сме само враќање -1 бидејќи тоа е позиција

71
00:02:39,750 --> 00:02:40,990
дека не постои во низа.

72
00:02:40,990 --> 00:02:43,940
И така тоа значи дека кога ќе го добие назад од функцијата

73
00:02:43,940 --> 00:02:46,500
тој вели: "Хм, во ред. Претпоставувам дека не најдовме ништо.

74
00:02:46,500 --> 00:02:47,930
Така што никогаш 500 беше таму. "

75
00:02:47,930 --> 00:02:49,700
На убаво нешто за линеарно пребарување е дека

76
00:02:49,700 --> 00:02:51,060
тоа ќе работат на било која листа на предмети,

77
00:02:51,060 --> 00:02:52,950
без оглед на тоа колку предмети се нареди.

78
00:02:52,950 --> 00:02:55,540
Не е важно каде брокула е во производство коридор.

79
00:02:55,540 --> 00:02:57,070
Онолку колку што ќе одат надолу по патека од почетокот до крајот,

80
00:02:57,070 --> 00:02:58,470
вие сте обврзани да го најдете,

81
00:02:58,470 --> 00:03:00,800
претпоставувајќи продавницата не снема брокула, се разбира.

82
00:03:00,800 --> 00:03:04,200
Но тоа е најголема сила е исто така тоа е најголема слабост.

83
00:03:04,200 --> 00:03:05,340
Велат дека имаат листа на двесте броеви

84
00:03:05,340 --> 00:03:06,930
кои се подредени 1-200.

85
00:03:06,930 --> 00:03:09,420
Ако сте во потрага за бројот 198,

86
00:03:09,420 --> 00:03:11,060
мора да се бара речиси целата листа на броеви

87
00:03:11,060 --> 00:03:12,960
пред да се најде еден што го барате.

88
00:03:12,960 --> 00:03:14,460
Мора да постои подобар начин!

89
00:03:14,460 --> 00:03:15,890
Остатокот увери дека постои.

90
00:03:15,890 --> 00:03:17,440
Но, тоа е тема за друг видео.

91
00:03:17,440 --> 00:03:19,280
Исто така, не се секирај!

92
00:03:19,280 --> 00:03:22,650
Само затоа што линеарно пребарување не е најдобро решение за сите ситуации,

93
00:03:22,650 --> 00:03:24,190
тоа не значи дека тоа не доаѓа во удобен.

94
00:03:24,190 --> 00:03:27,130
Инаку, како ќе најдете дека брокулата во производство патека?

95
00:03:27,130 --> 00:03:29,910
Моето име е Патрик Шмид, и ова е CS50.

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